백준: 4963 섬의 개수

문제

4963번: 섬의 개수

 

문제 풀이

 주어진 지도에서 섬의 개수를 찾는 문제이다. 2667 단지번호붙이기와 유사한 문제이지만 경우의 수가 추가된 문제이다. 상하좌우뿐 아니라, 대각선으로 인접한 경우도 같은 섬으로 판단한다. 즉, 위의 그림과 같이 하나의 점에서 총 8방향으로 탐색을 진행하면 된다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < h and 0 <= y < w and graph[x][y]


def bfs(start):
    q = deque([start])
            # 상, 하, 좌, 우
    dirs = ((-1, 0), (1, 0), (0, 1), (0, -1),
            # 대각선
            (-1, 1), (-1, -1), (1, -1), (1, 1))

    while q:
        cur_x, cur_y = q.popleft()
        for x, y in dirs:
            next_x, next_y = cur_x + x, cur_y + y
            if visitable(next_x, next_y):
                graph[next_x][next_y] = 0
                q.append([next_x, next_y])

    return 1

if __name__ == "__main__":
    while True:
        w, h = map(int, stdin.readline().split())

        if not w and not h:
            break

        graph = [list(map(int, stdin.readline().split())) for _ in range(h)]
        answer = 0
        print(graph)
        for x in range(h):
            for y in range(w):
                if graph[x][y]:
                    graph[x][y] = 0
                    answer += bfs([x, y])
        print(answer)

 보통 그래프를 N * M으로 주는 반면 이 문제는 W, H로 주어 x, y의 범위를 H, W로 하여야 한다는 차이도 있다.