[BOJ 4963] 섬의 개수 (Python)

풀이

직전에 포스팅했던 나이트의 이동과 굉장히 유사한 문제라고 생각했으며 BFS 개념을 알고, 혼자서 구현할 수 있다면 쉽게 풀 수 있을 것으로 생각한다. 주의할 점은 8방 탐색이라는 점과 섬의 영역(이어진 땅들의 모임)을 저장하는 변수의 위치라고 생각한다. 간략하게 로직을 설명하겠다.

1. (0, 0) ~ (h, w) 까지 탐색을 수행한다. 단, 땅이면서(=1) 이전 탐색 때 방문하지 않은 좌표에 대해서 BFS 탐색을 수행한다!

2. BFS 탐색 과정에서 8방 탐색을 수행하며, 다음으로 탐색할 좌표가 땅이면서(=1) 방문하지 않은 좌표라면 큐에 삽입하여 다음 BFS 탐색을 준비한다.

3. 위 과정을 종료 될 때까지 반복한다. (즉, 1번의 BFS 탐색이 수행되면 섬의 영역 (이어진 땅들의 모임) 1개가 추가된다.)

코드

import sys
from collections import deque

input = sys.stdin.readline
dir = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [1, -1], [-1, 1], [1, 1]]


def bfs(arr, r, c, visited):
    q = deque([(r, c)])
    visited[r][c] = True

    while q:
        x, y = q.popleft()
        for i in range(8):
            nx, ny = x + dir[i][0], y + dir[i][1]
            # 지도 안에 있으면서
            if 0 <= nx < len(arr) and 0 <= ny < len(arr[0]):
                # 방문하지 않았고, 땅인 지점만 (--> 섬을 찾기 위한 과정)
                if not visited[nx][ny] and arr[nx][ny] == 1:
                    visited[nx][ny] = True
                    q.append((nx, ny))


while True:
    col, row = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(row)]
    visited = [[False] * col for _ in range(row)]
    sector = 0

    if col == 0 and row == 0:
        break

    for r in range(row):
        for c in range(col):
            if board[r][c] == 1 and not visited[r][c]:
                bfs(board, r, c, visited)
                # bfs() 1번 수행되면 섹터(섬의 영역 = 이어진 땅들의 모임) 1개가 추가된다.
                sector += 1

    print(sector)