섬의 갯수_4963_Python

대각선으로 연결된 요소 갯수 구하기

문제

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

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

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

문제 접근

해당 문제는 연결요소의 갯수를 구하는 문제이지만, 주의해야 할 점은 상하좌우 뿐만 아니라 대각선으로 연결된 것도 포함해야 한다.

위의 그림에서 볼 수 있듯이 빨간색으로 섬들이 연결되어 있다.
따라서 연결요소의 갯수는 위 그림에서 3개이다.

문제 해결

연결요소의 갯수를 세기위해 BFS(너비 우선 탐색)을 생각해볼 수 있다.
이때 dx와 dy의 4번째 요소까지는 상하좌우를 고려한 것이고,
5번째요소부터 8번째요소까지는 대각선 이동을 고려한 것이다.
상화좌우 대각선을 이동해가며 육지라면, 큐에 요소를 추가해주면서 연결요소의 갯수를 세어볼 수 있다.

def BFS(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        now = queue.popleft()
        dx = [1, 0, -1, 0, 1, -1, 1, -1]
        dy = [0, 1, 0, -1, 1, -1, -1, 1]
        for k in range(8):
            X = now[0] + dx[k]
            Y = now[1] + dy[k]
            if 0 <= X < h and 0 <= Y < w:
                if not visited[X][Y]:
                    if land[X][Y] == 1:
                        visited[X][Y] = True
                        queue.append((X, Y))

전체 코드

import sys
from collections import deque
input = sys.stdin.readline


def BFS(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        now = queue.popleft()
        dx = [1, 0, -1, 0, 1, -1, 1, -1]
        dy = [0, 1, 0, -1, 1, -1, -1, 1]
        for k in range(8):
            X = now[0] + dx[k]
            Y = now[1] + dy[k]
            if 0 <= X < h and 0 <= Y < w:
                if not visited[X][Y]:
                    if land[X][Y] == 1:
                        visited[X][Y] = True
                        queue.append((X, Y))


while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    land = []
    for _ in range(h):
        land.append(list(map(int, input().split())))
    visited = [[False] * w for _ in range(h)]
    answer = 0
    for i in range(h):
        for j in range(w):
            if land[i][j] == 0:
                visited[i][j] = True
    for i in range(h):
        for j in range(w):
            if not visited[i][j]:
                BFS(i,j)
                answer += 1

    print(answer)