[Python] 섬의 개수 - 백준 (DFS)

해당 글은 백준 4963번 '섬의 개수' 문제를 다룬다.

문제

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

설명

해당 문제는 DFS나 BFS로 간단하게 해결할 수 있다.

여기서는 DFS를 통해 해결하였고, 1은 섬, 0은 바다로 표시되어 있으므로 카운트를 2부터 시작하여 DFS를 진행하고 결과 출력시 -2를 해주어 섬의 개수를 세어주었다.

그리고 주의할 점은 재귀 한계를 늘려주어야 에러가 발생하지 않는다.

 

코드

import sys
sys.setrecursionlimit(1000000)

dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, -1, 1, -1, -1, 1, 1]

def dfs(x, y, cnt):
    arr[x][y] = cnt
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < h and ny >= 0 and ny < w:
            if arr[nx][ny] == 1:
                dfs(nx, ny, cnt)

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    arr = [list(map(int, input().split())) for _ in range(h)]
    cnt = 2
    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1:
                dfs(i, j, cnt)
                cnt += 1
    print(cnt-2)