[백준 - Python] 4963. 섬의 개수 (DFS/BFS)

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

4963번: 섬의 개수

 

코드

from collections import deque

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

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

    mat = []
    for i in range(h):
        mat.append(list(map(int, input().split())))

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

    def bfs(x, y):
        queue = deque([(x, y)])
        mat[x][y] = 0
        while queue:
            x, y = queue.popleft()
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]

                if nx < 0 or nx >= h or ny < 0 or ny >= w:
                    continue

                if mat[nx][ny] == 1:
                    queue.append((nx, ny))
                    mat[nx][ny] = 0

    cnt = 0
    for x in range(h):
        for y in range(w):
            if mat[x][y] == 1:
                bfs(x, y)
                cnt += 1

    print(cnt)

 

유기농 배추 문제와 유사하게 연결 요소의 개수를 구하는 문제였다.

한 가지 다른 점이 있다면, 연결 방향이 상하좌우 말고 대각선 4방향이 추가로 더 가능하다는 점이다.

 

bfs를 따로 함수로 빼서 구현을 했고,

bfs를 수행해야 하는 때는 주어진 2차원 배열을 이중 반복문을 돌면서

1인 경우에 섬이 존재하는 경우이므로

탐색을 시작하도록 구현하였다.

 

탐색이 완료된 지점은 0으로 변경해 방문 완료 처리를 해주었다.

 

w와 h는 50보다 작거나 같은 양의 정수라면서, 왜 0 처리 안해주면 런타임 에러 나는 거냐?