[Python] 2468번 안전 영역

✏️ 문제

 

문제 파악

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

• 0 → 방문 안한 영역
• 1 → 방문한 영역
• -1 → 물에 잠긴 부분으로 방문하면 안되는 영역

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

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

 

water라는 변수의 값을 0 ~ (지역의 최대 높이)로 주어 for 반복문을 도는 코드를 짰다.

안전한 영역의 최대 개수를 구하므로 max(이전의 안전한 영역 개수, 현재 안전한 영역 개수)로 하여 결과값을 구했다.

 

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

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

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

 

알고리즘

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

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

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n = int(input())
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
graph = [[0] * n for _ in range(n)]
visited = [[0] * n for _ in range(n)]
max_n = 0

for i in range(n):
  num = list(map(int, input().split()))
  for j in range(n):
    graph[i][j] = num[j]
    if num[j] > max_n:
      max_n = num[j]
 
def dfs(x, y, water):
  visited[x][y] = 1

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

    if 0 <= dx < n and 0 <= dy < n and visited[dx][dy] == 0 and graph[dx][dy] > water:
      dfs(dx, dy, water)

area = 0  
for water in range(0, max_n+1):
  visited = [[0] * n for _ in range(n)]

  for i in range(n):
    for j in range(n):
      if graph[i][j] <= water:
        visited[i][j] = -1 # 방문하면 안되는 영역
  
  pre_area = 0
  for i in range(n):
    for j in range(n):
      if visited[i][j] == 0:
        dfs(i, j, water)
        pre_area += 1

  area = max(area, pre_area)

print(area)

 

 

 

---

 

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

[알고리즘] DFS와 BFS