[알고리즘] 백준4963 섬의 개수 - 파이썬

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

4963번: 섬의 개수

 

 

[풀이 코드]

from sys import stdin
from collections import deque

input = stdin.readline

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

def bfs(i, j):
    queue = deque()
    queue.append((i, j))

    while queue:
        x, y = queue.popleft()

        for d in range(8):
            nx = dx[d] + x
            ny = dy[d] + y

            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break

    graph = []
    for _ in range(h):
        graph.append(list(map(int, input().split())))

    cnt = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)

- 섬의 개수를 세는 문제이고 땅은 1, 바다는 0이다. 땅은 가로, 세로뿐만 아니라 대각선도 가능하기 때문에 위의 코드에서 dx, dy 배열 원소를 통해 8쌍으로 표현할 수 있다.

 

- bfs함수는 전에 풀어왔던 문제처럼 같은 방식이다.