[Python 파이썬] 백준 4963번 - 섬의 개수

2024년 8월 9일

문제 링크 : 백준 4963번 - 섬의 개수

문제

 

 

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

 

문제 접근

 

암시적 그래프에서의 탐색 문제이며, 한 육지 블록을 시작점으로 지정하였을 때, 해당 육지와 이어진 다른 육지 블록들을 찾아 하나의 섬으로 간주하여 총 몇 개의 섬이 존재하는지 알아내는 문제이다.

 

이 문제는 대각선으로 인접한 육지 블록 또한 이어진 것으로 간주하므로, 상하좌우 + 대각선의 총 8방향으로 탐색을 진행해야 한다는 특징이 있다.

 

8방향 탐색은 다음과 같은 코드로 구현하였다.

# 동, 동남, 남, 남서, 서, 북서, 북, 북동
d_row = [0, 1, 1, 1, 0, -1, -1, -1]
d_col = [1, 1, 0, -1, -1, -1, 0, 1]

# now_row, now_col : 현재 탐색중인 블록의 행/열 좌표
# next_row, next_col : 다음으로 탐색해볼 행/열 좌표
for i in range(8):
	next_row, next_col = now_row + d_row[i], now_col + d_col[i]

 

 

8방향으로 탐색을 진행해야 한다는 점 외엔 BFS 로직을 사용한다는 점에서 크게 차이점이 없다.

 

[0, 0]부터 [h - 1, w - 1]까지 육지 블록인지 확인하여, 만약 아직 방문하지 않은 육지블록의 좌표를 찾았다면 해당 좌표를 BFS의 시작점으로 설정하고 BFS 로직을 통해 인접한 육지 블록들에 모두 방문 체크를 해주며 진행하였다.

 

최종적으로 BFS를 수행한 횟수가 곧 정답이 되는 것이다.

---

입력 예제

 

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

 

 

 

출력 예제

 

0
1
1
3
1
9

 

 

---

전체 코드

 

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

def bfs(start_row, start_col):
    # 동, 동남, 남, 남서, 서, 북서, 북, 북동
    d_row = [0, 1, 1, 1, 0, -1, -1, -1]
    d_col = [1, 1, 0, -1, -1, -1, 0, 1]

    queue = deque()
    queue.append([start_row, start_col])
    visited[start_row][start_col] = True

    while queue:
        now_row, now_col = queue.popleft()
        for i in range(8):
            next_row, next_col = now_row + d_row[i], now_col + d_col[i]
            if 0 <= next_row < h and 0 <= next_col < w:
                if not visited[next_row][next_col] and board[next_row][next_col] == 1:
                    queue.append([next_row, next_col])
                    visited[next_row][next_col] = True

if __name__ == "__main__":
    while True:
        w, h = map(int, input().split())
        if w == h == 0:
            break
        board = []
        visited = [[False for _ in range(w)] for _ in range(h)]
        for _ in range(h):
            board.append(list(map(int, input().split())))

        cnt = 0

        for row in range(h):
            for col in range(w):
                if board[row][col] == 1 and not visited[row][col]:
                    bfs(row, col)
                    cnt += 1
        print(cnt)

 

---

풀이 후기

 

8방향으로 탐색하는 암시적 그래프 문제는 오랜만이었다.

 

문제를 제대로 안 읽고 4방향 탐색을 진행했다가 섬의 개수가 많이 출력되길래 대체 뭐가 잘못된거지..? 하고 문제보다 코드를 먼저 봤던 기억이 있다. 문제를 항상 꼼꼼히 읽자!!