[백준][4963] 섬의 개수

• 문제
  • 4963번: 섬의 개수
• 해설

import sys

sys.setrecursionlimit(99999)

def get_data():
    width, height = [int(x) for x in sys.stdin.readline().split()]
    if height == 0:
        sys.exit()
    mapping = []
    for x in range(height):
        mapping.append([int(z) for z in sys.stdin.readline().split()])
    return width, height, mapping

def chk_in_map(x, y, mapping):
    return 0 <= x < len(mapping) and 0 <= y < len(mapping[0])

dx_list = [-1, 0, 1]
dy_list = [-1, 0, 1]

def dfs(x, y, chk, mapping, ans):
    chk[x][y] = True
    ans += 1
    for dx in dx_list:
        for dy in dy_list:
            if dx == 0 and dy == 0:
                continue
            cand_x = x + dx
            cand_y = y + dy
            if chk_in_map(cand_x, cand_y, mapping) and mapping[cand_x][cand_y] == 1 and not chk[cand_x][cand_y]:
                dfs(cand_x, cand_y, chk, mapping, ans)
    return ans

for _ in range(999999999):
    ans = 0
    width, height, mapping = get_data()
    chk = [[False for z in range(width)] for q in range(height)]
    for x in range(height):
        for y in range(width):
            if mapping[x][y] and not chk[x][y]:
                ans = dfs(x, y, chk, mapping, ans)
    print(ans)

• 포인트
  • dfs