[Python] 4963번 섬의 개수

✏️ 문제

 

문제 파악

나는 visited 2차원 배열의 값을 세 가지로 나눠서 대입하고 이를 이용해 조건문을 구분하였다.

• 0 → 방문 안한 섬
• 1 → 방문한 섬
• -1 → 바다인 부분으로 방문하면 안되는 위치

또한 이 문제의 경우 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 건너갈 수 있으므로 방향 배열을 다음과 같이 구성했다.

d = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]

 

아! 그리고 이 문제는 DFS로 풀 때 재귀를 사용해서 풀면 RecursionError 에러가 발생한다. 이는 Python이 정한 최대 재귀 깊이보다 내 코드의 재귀의 깊이가 더 깊어서 발생하는데 이를 해결하는 방법은 2가지가 있다.

1. 재귀 함수를 사용하지 않고 스택으로 DFS 구현
2. sys.setrecursionlimit() 사용

나는 2번째 방법으로 해결했다!

 

알고리즘

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

 

 

코드

• sys.setrecursionlimit() 사용으로 최대 재귀 깊이를 변경했을 때

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

while True:
  w, h = map(int, input().split())
  d = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
  graph = [[0] * w for _ in range(h)]
  visited = [[0] * w for _ in range(h)]

  if w == 0 and h == 0:
    break

  for i in range(h):
    num = list(map(int, input().split()))
    for j in range(w):
      graph[i][j] = num[j]
      if num[j] == 0:
        visited[i][j] = -1
  
  def dfs(x, y):
    visited[x][y] = 1

    for i in range(8):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < h and 0 <= dy < w and visited[dx][dy] == 0 and graph[dx][dy] == 1:
        dfs(dx, dy)

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

  print(area)

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS