백준 알고리즘 4963번 섬의 개수 - 파이썬

www.acmicpc.net/problem/4963

4963번: 섬의 개수

기본적인 DFS 문제였다. 여타 다른 문제에서 일반적으로 4방향을 검사하는 것과 다르게 총 8방향을 검사하도록 풀었다. 다만, RecursionError: maximum recursion depth exceeded while calling a Python object 가 발생해서 인터넷 검색을 통해 recursion limit을 늘려주었다.

import sys
sys.setrecursionlimit(10**4)
# 상, 하, 좌, 우, 상좌, 상우, 하좌, 하우
dx = [-1, 1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]


def dfs(graph, visited, x, y, w, h):
    if visited[x][y] or graph[x][y] == 0:
        return
    visited[x][y] = True
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < h) and (0 <= ny < w) and not visited[nx][ny] and graph[nx][ny] == 1:
            dfs(graph, visited, nx, ny, w, h)


while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    graph = []
    visited = [[False] * w for _ in range(h)]
    for _ in range(h):
        graph.append(list(map(int, input().split())))

    result = 0

    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1 and not visited[i][j]:
                dfs(graph, visited, i, j, w, h)
                result += 1
    print(result)