[백준] 4963번 섬의 개수 - 파이썬

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

4963번: 섬의 개수

풀이:

재귀 dfs를 사용해서 풀었다.

기본 dfs 문제와 달랐던 점은 상, 하, 좌, 우 뿐만 아니라 대각선도 확인해줘야 한다는 것이였다.

그래서 확인 범위를 총 8개로 늘렸더니 성공했다. 

앞으로는 재귀를 사용할 때 sys.setrecursionlimit(10**6)를 적어야 한다는 점을 잊지 말아야겠다.

 

import sys
sys.setrecursionlimit(10**6)
def dfs(y, x):
    if y <= -1 or y >= h or x <= -1 or x >= w or grid[y][x] != 1:
        return
    grid[y][x] = 0
    for i in range(8):
        dfs(y + dy[i], x + dx[i])

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

while True:
    w, h = map(int, input().split())

    if w == 0 and h == 0:
        break

    grid = []

    for _ in range(h):
        grid.append(list(map(int, input().split())))

    count = 0

    for y in range(h):
        for x in range(w):
            if grid[y][x] == 1:
                dfs(y, x)
                count += 1

    print(count)