boj 2468 안전영역(실버1)

boj 2468 안전영역

dfs로 풀어주었다.
내린 비의 양을 기준으로 삼아 그것보다 큰 영역들만 탐색해 나가며 섬이 몇덩이가 생성되는지 체크한다.
그렇게 맥스값을 저장하면서 올수있는 비의 모든 경우의수를 따져 가장 큰 맥스값을 출려해준다.
전형적인 dfs문제이지만, 최대값을 구해야하기에 For문을 한번 더 돌려서 최대값을 체크만 해주면 되는 문제라 생각된다!

내풀이

import sys
sys.setrecursionlimit(100000)

n = int(input())

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

maxx = max(map(max,back)) ##최대값

y = [0,-1,0,1]
x = [1,0,-1,0]
countarr = []

def dfs(a,b,rain):
  if a < 0 or b < 0 or a >=n or b >=n :
    return False

  if visited[a][b] == 0 and back[a][b] > rain:
    visited[a][b] = 1
    dfs(a-1,b,rain)
    dfs(a+1,b,rain)
    dfs(a,b-1,rain)
    dfs(a,b+1,rain)
    return True

  else :
    return False


for rain in range(maxx):
  visited = [[0]*n for _ in range(n)]
  count = 0
  for i in range(n):
    for j in range(n):
      if back[i][j] > rain:
        if dfs(i,j,rain):
          count += 1
  # print(count)

  countarr.append(count)

print(max(countarr))

회고

재귀를 통해 dfs를 구현해 주었고, 파이썬의 재귀 맥시멈 제한을 넉넉하게 10^5로 올려주었다.
이 문제의 경우 재귀리미트 설정 안해주면 에러난다!

결과