[백준] 4963번, 섬의 개수 (Python)

문제

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

4963번: 섬의 개수

 

코드

import collections

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    graph = [list(map(int,input().split())) for _ in range(h)]
    check = [[False]*w for _ in range(h)]
    
    def bfs(x,y):
        queue = collections.deque()
        queue.append((x,y))
        dx, dy = [-1, 1, 0, 0, -1, -1, 1, 1], [0, 0, -1, 1, -1, 1, -1, 1]
        while queue:
            x, y = queue.popleft()
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if graph[nx][ny] == 1 and check[nx][ny] == False:
                        check[nx][ny] = True
                        queue.append((nx,ny))
    count = 0
    for x in range(h):
        for y in range(w):
            if check[x][y] == False and graph[x][y] == 1:
                bfs(x,y)
                count += 1
    print(count)

섬은 가로, 세로, 대각선으로 이어져있으면 하나의 섬으로 본다.

그래서 dx, dy에 상하좌우 대각선을 포함하여 좌표를 넣어주고 8방면 모두 돌아준다.

 

섬이 이어져 있으면 하나의 섬으로 카운트하기 때문에 bfs 함수 실행횟수와 같게된다.