[백준/2468/파이썬] 안전영역 - DFS(재귀)

---

소스코드

import sys

sys.setrecursionlimit(100000)

N = int(sys.stdin.readline())

area = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]  #입력받기

dx = [-1,1,0,0]

dy = [0,0,1,-1]

def dfs(x,y,h):       #범위내 조건을 만족하면 재귀 돌면서 실행

  for i in range(4):

    nx = x + dx[i]

    ny = y + dy[i]

    if (0<=nx<N) and (0<=ny<N) and (area[nx][ny]>h) and not(visited[nx][ny]):

      visited[nx][ny] = True

      dfs(nx,ny,h)

ans = 1

for i in range(101):        #높이비교

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

  cnt = 0

  for j in range(N):

    for k in range(N):

      if (area[j][k]>i) and not(visited[j][k]):   #비가 온거보다 높고 방문하지 않았으면

        cnt += 1

        visited[j][k] = True

        dfs(j,k,i)

  ans = max(ans, cnt)

print(ans)

---

알고리즘

이번 문제는 오류란 오류는 다 만난듯한 문제였다.

import sys

sys.setrecursionlimit(100000)

일단 이친구를 안해주면 dfs가 계속 돌아가서 recursion 오류가 났다. 그래서 dfs의 깊이 설정을 꼭 해줘야한다고 한다.

시간초과, RTE,,,등등

높이는 문제에서 1~100이라고 했으니 마지막 비의 높이 비교하는 for문에서 101까지 선언해줬다.

이후로는 평범하게 재귀 dfs를 실행하면 되는 문제였다.