4963 - 섬의 개수
문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def dfs(x, y, visited):
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(nx, ny, visited)
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]
while True:
w, h = map(int, input().split())
if w == 0 and h == 0:
exit()
graph = [list(map(int, input().split())) for _ in range(h)]
visited = [[False] * w for _ in range(h)]
count = 0
for i in range(h):
for j in range(w):
if graph[i][j] == 1 and not visited[i][j]:
dfs(i, j, visited)
count += 1
print(count)한마디
섬의 개수 문제는 아주 기본적인 DFS 문제이다. 상하좌우, 대각선까지 총 8개의 경로를 탐색하면 된다.
