백준 4963번 : 섬의 개수 in Python

4963번: 섬의 개수

 

www.acmicpc.net

이 문제는 섬과 바다 지도가 주어질 때 섬의 개수를 세는 문제이다. 단, 두 정사각형이 같은 섬에 있기 위해서는 두 정사각형이 가로, 세로 또는 대각선으로 인접하고 있어야 한다.

이는 그래프 탐색을 이용해 쉽게 해결할 수 있다. 우선 깊이 우선 탐색이나 너비 우선 탐색 중 하나를 구현한 뒤, 지도 내 모든 정사각형을 방문하면서 만약 해당 정사각형이 섬의 일부인 경우 그 정사각형과 연결되어 있고, 섬의 일부인 모든 정사각형을 방문하는 그래프 탐색을 진행한다. 그러면 이후 그 섬을 다시 방문했을 경우 이미 방문한 섬이기에 섬의 개수를 셀 때 영향을 끼치지 않는다. 

단, 보통 문제와는 달리 두 정사각형이 가로, 세로, 또는 대각선으로 인접한 경우 하나의 섬 내에 있다고 간주하므로 대각선 방향 역시 고려해야 한다.

이를 코드로 구현하면 다음과 같다.

import sys
sys.setrecursionlimit(10**5)
# DFS 구현
def DFS(x, y):
    if visited[x][y]: return
    visited[x][y] = True
    # 가로, 세로, 대각선 방향으로 인접한 정사각형을 방문하기 위한 보조 배열
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    for i in range(8):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # 인접한 정사각형 중 섬의 일부인 경우에만 DFS를 재귀적으로 호출한다.
        if 0<=next_x<h and 0<=next_y<w and m[next_x][next_y] == 1:
            DFS(next_x, next_y)
while True:
    w, h = map(int, input().split())
    # 입력의 마지막 줄에 0이 두 개 주어진다.
    if w == 0 and h == 0: break
    m = []
    for _ in range(h):
        m.append(list(map(int, input().split())))
    # 섬의 개수
    cnt = 0
    # 각 정사각형을 방문했는지를 알려주는 배열
    visited = [[False]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if not visited[i][j] and m[i][j] == 1:
                DFS(i, j)
                cnt += 1
    print(cnt)