백준 4963 섬의 개수 (Python)

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

4963번: 섬의 개수

전형적인 그래프 탐색 문제이다.

BFS로 풀든, DFS로 풀든 상관 없을 것이라고 생각한다.

 

visited 배열을 만들어 방문했던 기록을 남기고, 만약 방문했던 곳이라면 해당 지역은 건너뛸 수 있도록 했다.

그리고 항상 그래프를 탐색할 때에는 구역 내에 있는 지 확인을 먼저 하고 진행할 수 있도록 했다.

만약 땅이 맞다면, 방문을 한다는 의미로 visited를 True로 바꾸고 다음에 방문을 진행할 need_visit 배열에 추가하도록 했다.

 

import sys

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

while True:

    w, h = map(int, sys.stdin.readline().split())

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

    land = list()
    visited = [[False for _ in range(w)] for _ in range(h)]

    result = 0

    for _ in range(h):
        land.append(list(map(int, sys.stdin.readline().split())))

    for height in range(h):
        for width in range(w):

            if visited[height][width] is True:
                continue

            if land[height][width] == 0:
                visited[height][width] = True
                continue

            result += 1

            need_visit = [[height, width]]
            visited[height][width] = True

            while need_visit:
                cur_height, cur_width = need_visit.pop(0)

                for i in range(8):
                    target_height, target_width = cur_height + dy[i], cur_width + dx[i]
                    if 0 <= target_height < h and 0 <= target_width < w and land[target_height][target_width] == 1 and not visited[target_height][target_width]:
                        need_visit.append([target_height, target_width])
                        visited[target_height][target_width] = True

    print(result)