[TIL] 백준 4963 - 섬의 개수 ( python )

📌 문제 탐색하기

w : 지도의 너비

h : 지도의 높이

한 정사각형과 가로, 세로, 또는 대각선으로 연결되어 있는 사각형은 하나의 섬이고 섬의 개수를 구하는 것이 핵심입니다.

w, h는 50보다 작거나 같은 양의 정수입니다.

가능한 시간복잡도

지도의 전체 크기는 최대 50 * 50 = 2,500 정사각형입니다.

한 번 방문한 정사각형마다 8방향(가로, 세로, 대각선)의 인접 칸을 확인합니다.

따라서 최악의 경우 2,500 * 8 = 20,000번 정도의 연산이 수행됩니다.

하나의 탐색 당 최대 O(8 * w * h)안에 탐색을 해야 시간안에 탐색을 완료할 수 있습니다.

알고리즘 선택

지도의 크기가 크지 않아 재귀 깊이나 오버헤드에 대한 부담이 적으므로, 보다 직관적인 깊이 우선 탐색(DFS) 알고리즘을 활용하여 문제를 해결하고자 합니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. 지도의 너비와 높이가 0일때, 반복문을 종료합니다.
3. 방문 체크를 위한 visited 배열을 초기화합니다.(False)
4. 섬의 개수를 세기 위한 count변수를 설정합니다.
5. DFS 탐색을 수행합니다.
   1. 지도에서 땅(1)이고 아직 방문하지 않은 위치를 발견하면 DFS 탐색을 수행합니다.
   2. DFS는 해당 위치를 방문 처리한 후, 가로/ 세로/ 대각선 8 방향을 탐색하여 연결된 땅을 모두 방문 처리합니다.
6. DFS 탐색이 완료되면 하나의 섬을 발견한 것이므로 count를 증가시킵니다.
7. 섬의 개수를 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

1회차

• RecursionError가 발생했습니다.
  • sys.setrecursionlimit(int(1e6))을 사용하여 최대 재귀 호출 가능 횟수를 1,000,000으로 늘려, 깊은 재귀 호출이 필요한 경우에도 정상적으로 실행될 수 있도록 했습니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e6))

dy = [1, 0, -1, 0, -1, -1, 1, 1]
dx = [0, -1, 0, 1, -1, 1, -1, 1]

def dfs(y, x):
    global visited
    
    visited[y][x] = True
    
    for i in range(8):
        ny = y + dy[i]
        nx = x + dx[i]
        
        if 0 <= ny < h and 0 <= nx < w and matrix[ny][nx] == 1 and not visited[ny][nx]:
            dfs(ny, nx)

while True:
    w, h = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(h)]
    visited = [[False] * w for _ in range(h)]
    count = 0
    
    if w == 0 and h == 0:
        break
    
    for y in range(h):
        for x in range(w):
            if matrix[y][x] == 1 and not visited[y][x]:
                dfs(y, x)
                count += 1
                
    print(count)