[탐색/BFS] 백준 4963 섬의 개수 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

4963번: 섬의 개수

 

 

 

2. 문제 풀이

 섬의 개수를 세는 문제입니다.

 

2022.02.23 - [Algorithm] - [탐색/BFS] 백준 1012 유기농 배추 - Python

[탐색/BFS] 백준 1012 유기농 배추 - Python

 위 문제와 유사합니다. BFS 탐색으로 인근 땅이 없을 때까지 조사하고, BFS 탐색횟수로 섬의 개수를 구합니다.

 

 

 

3. 코드

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


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

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

    # BFS 탐색
    cnt = 0  # 섬의 개수
    for i in range(h):
        for j in range(w):
            # 땅이 있으면 bfs 탐색 시작
            if board[i][j] == 1:
                cnt += 1
                queue = deque([(i, j)])
                board[i][j] = 0

                # 상하좌우, 대각선 8방향 탐색
                direction = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (-1,-1), (1,-1), (-1,1)]
                while queue:
                    x, y = queue.popleft()

                    for dx, dy in direction:
                        nx, ny = x+dx, y+dy
                        # 지도를 벗어나지 않은 땅이 있다면 탐색
                        if 0 <= nx < h and 0 <= ny < w and board[nx][ny] == 1:
                            board[nx][ny] = 0
                            queue.append((nx, ny))
    print(cnt)

 '대각선' 방향의 땅도 이어져있는 걸로 칩니다. 이 점만 주의해서 8방향으로 탐색합니다.

 탐색된 땅은 0(바다)로 바꾸면서, (0, 0)부터 (h-1, w-1)까지 BFS 탐색합니다.