[백준] 4963번 문제 (섬의 개수) 파이썬(Python) 풀이

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

4963번: 섬의 개수

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def dfs(i, j):
    if i < 0 or j < 0 or i >= h or j >= w or mtx[i][j] == 0:
        return

    mtx[i][j] = 0

    dfs(i + 1, j)
    dfs(i, j + 1)
    dfs(i - 1, j)
    dfs(i, j - 1)
    dfs(i - 1, j - 1)
    dfs(i + 1, j + 1)
    dfs(i + 1, j - 1)
    dfs(i - 1, j + 1)

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        sys.exit(0)

    lands = 0
    mtx = [list(map(int, input().split())) for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if mtx[i][j] == 1:
                dfs(i, j)
                lands += 1

    print(lands)

재밌는 문제였다.

dfs함수로 주어진 섬의 범위를 넘지 않는 선에서 재귀를 통해 동, 서, 남, 북, 4방향의 대각(총 8방향)으로 탐색을 한다.

탐색을 하면서 1이었던 섬의 표시를 0으로 바꿔주어 탐색이 끝난 섬은 더이상 탐색을 하지 않게 방지하고,

모든 섬을 탐색하며 섬의 개수를 세어준다.