[백준/Python] 4963 섬의 개수

 

📌문제 탐색하기

w : 지도의 너비, h : 지도의 높이 (w, h은 50보다 작거나 같은 양의 정수)
w x h 지도의 각 칸은 땅(1) 또는 바다(0)이다.

한 땅에서 가로, 세로, 대각선으로 연결되어 있는 땅은 걸어갈 수 있다고 판단한다.
서로 걸어갈 수 있는 땅의 집합을 '섬'이라고 할 때, 주어진 지도에서 섬의 개수를 구하기

 

주어진 지도를 2차원 배열로 표현할 수 있고, 이 배열의 각 좌표는 정점이고 각 땅에서 가로, 세로, 또는 대각선으로 연결된 다른 땅까지의 경로를 간선으로 볼 수 있다.

 

알고리즘 선택

이 문제의 본질은 그래프에서의 연결 요소를 찾는 문제이다. 즉 각 육지를 하나의 정점으로 보고, 그 육지와 연결된 다른 육지들을 탐색하면서 그룹을 찾아야 한다. 따라서 그래프 탐색 중 BFS, DFS 어느 것을 사용해도 크게 상관 없다. 이번에는 DFS로 구현해보고자 한다.

 

DFS의 시간복잡도는 O(정점 개수 + 간선 개수)이다. 정점 개수는 최대 50*50=2500, 간선 개수는 8*2500 = 20000 정도 시간복잡도는 최대 O(2500 + 20000) 정도로, 시간 안에 탐색이 가능하다.

 

DFS로 풀 수 있나?

• 주어진 데이터를 그래프 형태로 해석 가능한가?
  • 지도의 땅들(정점), 땅에서 걸어갈 수 있는 다른 땅으로 이동하는 경로(간선)
• 탐색 깊이가 너무 깊지 않은가?
  • DFS는 재귀적으로 깊이를 탐색하기 때문에 탐색 깊이가 너무 깊어지면 재귀 호출 한계를 넘을 수 있다. 
  • 이 문제는 가로, 세로의 최대가 50으로 제한되어 있기 때문에 크게 문제가 없다.
•  최단 경로를 찾는 문제가 아닌가?
  • 최단 경로를 찾는 문제라면 DFS 외의 알고리즘을 선택하는 것이 적합함
  • 이 문제는 컴포넌트를 찾는 문제

---

📌코드 설계하기

1. 각 테스트 케이스마다 너비(w), 높이(h)를 입력받고, 해당하는 크기의 이차원 배열(map_data)을 생성한다.
2. 이차원 배열에 지도 정보를 저장한다.
3. 섬 개수 카운트용 변수(island_cnt)를 만든다.
4. 이차원 배열의 각 요소를 탐색하면서 아직 방문하지 않은 땅(1)을 방문하면, 섬 개수 카운트 변수에 1을 더하고 map_data에 해당 칸을 0으로 체크한 뒤, dfs 탐색을 시작한다.
5. 해당 정점에서 상, 하, 좌, 우, 대각선 방향으로 이동하면서 아직 방문하지 않은 땅(1)이면, 방문 체크 후 재귀적으로 dfs함수를 호출한다.
6. 이차원 배열의 모든 요소의 탐색이 끝나면, 섬 개수를 출력한다.

---

📌 시도 회차 수정 사항

1회차

• 런타임 에러 (RecursionError) 발생, 재귀 깊이 제한을 늘려주는 것을 깜빡했다..:)
  • sys.setrecursionlimit()로 재귀 깊이 제한을 늘려준다.
  • 이러한 문제를 방지하기 위해 스택 기반으로 DFS를 구현하는 것도 고려할 수 있다.

---

📌 정답 코드

import sys
sys.setrecursionlimit(10 ** 5)

delta = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
def dfs(x, y):
  for dx, dy in delta:
    nx, ny = x+dx, y+dy
    if 0 <= nx < h and 0 <= ny < w and map_data[nx][ny]:
      map_data[nx][ny] = 0
      dfs(nx, ny)

while True:
  w, h = map(int, input().split())
  if w == 0 and h == 0:
    break
  map_data = [list(map(int, input().split())) for _ in range(h)]
  island_cnt = 0

  for i in range(h):
    for j in range(w):
      if map_data[i][j]:
        island_cnt += 1
        map_data[i][j] = 0
        dfs(i, j)

  print(island_cnt)