백준 4963 파이썬 - 섬의 개수

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

4963번: 섬의 개수

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

코드

from collections import deque
import sys
dx = [1, -1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, -1, 1, -1, -1, 1, 1]
def bfs(a, b):
    s[a][b] = 0
    queue = deque()
    queue.append((a, b))
    while queue:
        x, y = queue[0][0], queue[0][1]
        queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == 1:
                s[nx][ny] = 0
                queue.append([nx, ny])
while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0:
        break
    s = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)

풀이

이 문제에서 주의할 점은 대각선으로 움직일 수 있으면 같은 섬이라는 것이다.

 

움직일 수 있는 8가지의 경우의 수를 x와 y축의 배열로 만들었다. 땅인 부분이 1로 주어지는데, 땅을 0으로 만들어 제거해주면서 BFS로 탐색하면 된다. cnt를 1씩 늘려주며 다 탐색한 후에 출력해준다.