[알고리즘] 백준 4963 섬의 개수 파이썬

📍 문제 탐색하기

섬의 개수 문제는 지도 형태로 주어진 땅과 바다의 배열에서 연결된 땅(1)을 찾아 섬의 개수를 세는 문제이다.
가로, 세로, 대각선으로 연결된 땅은 같은 섬으로 간주된다.

입력 범위

• 지도의 너비 w, 높이 h: 1 ≤ w,h ≤50
• 지도 데이터: 0 (바다), 1 (땅)
• 여러 테스트 케이스가 입력되며, 마지막에 w,h가 0,0이면 종료된다.

가능한 시간복잡도

• 각 지도 크기가 최대 50×50=2500
• 각 지점에서 8 방향을 모두 탐색하더라도, 탐색 범위는 여전히 w×h에 비례하다.
• 시간복잡도가 O(w×h)인 DFS나 BFS를 활용하면 효율적으로 해결 가능하다.

알고리즘 선택

• DFS를 사용하여 8 방향(상, 하, 좌, 우, 대각선)을 탐색하며 연결된 섬을 찾는다.
• 이후에 설명하겠지만, DFS는 재귀적으로 탐색하므로, 재귀 깊이 문제를 해결하기 위해 sys.setrecursionlimit을 조정했다.
• sys.setrecursionlimit는 오늘 문제를 풀면서 처음 알게되었다..!

---

📍 코드 설계하기

1. 문제의 입력을 받는다.

• 지도 크기 w, h와 땅/바다 데이터를 입력받는다.
• 0,0 입력이 들어오면 종료한다.

2. DFS 탐색 구현

• 8 방향으로 연결된 땅을 탐색한다.
• 탐색 중 방문한 지점은 visited 배열에 기록하여 중복 방문을 방지한다.

3. 섬의 개수 카운팅

• 모든 지점을 순회하며, 방문하지 않은 땅을 발견할 때마다 DFS로 연결된 모든 땅을 방문 처리하고 섬의 개수를 증가시킨다.

---

📍 시도 회차 및 수정 사항

1차 시도 (RecursionError 발생) ❌

import sys
input = sys.stdin.readline

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        sys.exit(0)

    land = [list(map(int, input().split())) for _ in range(h)]
    visited = [[False]*w for _ in range(h)]

    # 상, 하, 좌, 우 + 대각선(8방향)
    dx = [1, -1, 0, 0, 1, 1, -1, -1]
    dy = [0, 0, 1, -1, 1, -1, 1, -1]

    def dfs(r, c):
        visited[r][c] = True
        for i in range(8):
            nr = r + dy[i]
            nc = c + dx[i]

            if 0 <= nr < h and 0 <= nc < w:
                if land[nr][nc] == 1 and not visited[nr][nc]:
                    dfs(nr, nc)

    cnt = 0
    for i in range(h):
        for j in range(w):
            if land[i][j] == 1 and not visited[i][j]:
                cnt += 1  # 새로운 섬 발견
                dfs(i, j)

    print(cnt)

• 문제: 지도 크기가 커지고, 섬의 크기가 클 경우 재귀 깊이를 초과하여 RecursionError가 발생했다.

2차 시도 (RecursionError 해결) ✅

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        sys.exit(0)

    land = [list(map(int, input().split())) for _ in range(h)]
    visited = [[False]*w for _ in range(h)]

    # 상, 하, 좌, 우 + 대각선(8방향)
    dx = [1, -1, 0, 0, 1, 1, -1, -1]
    dy = [0, 0, 1, -1, 1, -1, 1, -1]

    def dfs(r, c):
        visited[r][c] = True
        for i in range(8):
            nr = r + dy[i]
            nc = c + dx[i]
            
            if 0 <= nr < h and 0 <= nc < w:
                if land[nr][nc] == 1 and not visited[nr][nc]:
                    dfs(nr, nc)

    cnt = 0
    for i in range(h):
        for j in range(w):
            if land[i][j] == 1 and not visited[i][j]:
                cnt += 1  # 새로운 섬 발견
                dfs(i, j)

    print(cnt)

• 해결: sys.setrecursionlimit(10000)으로 재귀 깊이를 증가시켜 문제를 해결했다.

---

📍 느낀점

최종적으로 이번 문제에선 sys.setrecursionlimit을 활용하여 기존 DFS 방식을 유지했지만, 효율적인 섬 탐색을 위해 BFS 또는 반복문 기반 DFS를 사용할 수도 있을 것 같다. 추가로 해 볼 예정이다!