BOJ 2468

Input

N = int(input())
latitude = [list(map(int, input().split())) for _ in range(N)]

DFS

recursion limit 설정하기

이 문제를 파이썬에서 풀기 위해서 무조건 sys.setrecursionlimit()을 추가해줘야 한다. 이 코드를 삽입하지 않으면 런타임 에러가 발생한다. 공식 도큐먼트에 의하면 해당 코드는 파이썬 인터프리터 stack에 최대 깊이를 지정하는 것이다. 무한대의 recursion이 발생해서 overflow가 발생하는 것을 방지하기 위함이다. 이 문제에서는 그 만큼 깊이 있게 recursion으로 stack이 쌓이기 때문에 어느 정도가 진행되면 제한을 둬야 하는 것이다.

ref > https://dojinkimm.github.io/problem_solving/2019/11/15/boj-2468-safezone.html

• recursion 을 사용할 때 runtime error 가 발생한다면 sys.setrecursionlimit() 을 설정하자!!

import sys
sys.setrecursionlimit(100000)

direction 배열 선언해놓기

• 배열로 x, y 한번에 만들어도 좋고
• x, y 따로 선언해서 같은 index로 접근해도 좋다.

dir = [[-1,0],[1,0],[0,-1],[0,1]]

visited 배열 생성하기

visited = [[0]*N for _ in range(N)]

조건

• 가능한 높이를 조건에 따라 세팅해놓고,
• 매번 비교하며 max 값을 구해야 하므로 기본 변수들을 초기화시킨다.

maxHeight = 100
for height in range(100):
  count = 0
  visited = [[0]*N for _ in range(N)]

• 영역을 연속적으로 구하는 것이므로, 동일한 조건을 동일하게 반복하며 실행한다 === DFS

def dfs(dy, dx):
  visited[dy][dx] = 1

  for d in dir:
    y = dy + d[0]
    x = dx + d[1]

    if 0 <= x < N and 0 <= y < N:
      if visited[y][x] == 0 and latitude[y][x] >= height:
        dfs(y, x)

• 2차원 배열을 모두 돌며 조건에 맞는 경우 DFS
  1. 방문하지 않음
  2. 고도가 기준보다 높거나 같음 (잠기지 않음)
• 이후 빠져나온 경우는 영역이 정해졌다는 의미이므로 count++ 를 실행한다.

for i in range(N): 
  for j in range(N):
    if visited[i][j] == 0 and latitude[i][j] >= height:
      # visited 체크용 (세트 만들기)
      dfs(i, j)
      count += 1

• 배열을 모두 검사하면 해당 height 에 대한 검사가 완료되었다는 뜻이므로 max 값을 구한다.

maxCount = max(maxCount, count)

Output

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

print(maxCount)