[DFS] 백준 #4963 섬의 개수 - Python

🗂️ 문제

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

 

 

💡 접근법

섬의 개수를 세기 위해 DFS를 통해 탐색한다.

이때 상하좌우뿐만 아니라 대각선으로 연결되어 있어도 하나의 섬으로 본다. 따라서 이를 고려하여 탐색해야 한다.

 

또한 파이썬의 최대 재귀 깊이가 1000이므로 의도적으로 깊이를 늘려줘야 한다. 그렇지 않으면 RecursionError가 발생한다.

 

😎 내 코드

import sys
sys.setrecursionlimit(10**6)

dx = [0, 0, -1, 1, 1, 1, -1, -1]  # 상하좌우 + 대각선
dy = [1, -1, 0, 0, 1, -1, 1, -1]

def DFS(y, x):
    visited[y][x] = True

    for ax, ay in zip(dx, dy):
        nx = x + ax
        ny = y + ay
        if w > nx >= 0 and h > ny >= 0:
            if maps[ny][nx] == 1 and not visited[ny][nx]:
                DFS(ny, nx)

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0:
        break

    maps = []
    for _ in range(h):
        maps.append(list(map(int, sys.stdin.readline().split())))

    visited = [[False] * w for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maps[i][j] == 1 and not visited[i][j]:
                cnt += 1
                DFS(i, j)

    print(cnt)

 

✅ 정답 확인