[코드트리/INTERMEDIATE LOW] DFS 안전지대 Python 파이썬

 

부제 : 코드트리 파이썬 런타임 에러 해결하기

 

🔥 문제 링크

https://www.codetree.ai/missions/2/problems/comfort-zone?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

🔥 문제 

 

🔥 풀이

✅ k 값을 늘려주면서 안전 지대 개수의 최대값을 갱신해주고 최대 안전 지대가 생기는 k 값을 찾아주면 되는 문제

     ✔️ k값이 100까지 가능하다지만 제일 높은 안전지대보다 k값이 커지게 되면 다 물에 잠기므로 안전지대가 0이 된다. 그래서 반복문을 제일 높은 숫자-1까지만 반복문을 돌려주었다.

 

✅ dfs이므로 재귀함수를 이용해 풀었음

 

⚠️ 런타임에러 폭탄을 받게 되다 ^^,,

- 첫번째 런타임 에러

Traceback (most recent call last):
어쩌구저쩌구
RecursionError: maximum recursion depth exceeded

백준 풀면서 많이 봤던 에러다.. Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때 나타나는 에러로 백준에서는 코드 제일 상단에서 최대 재귀 깊이를 변경해줌으로써 해결할 수 있었다.

import sys
sys.setrecursionlimit(10**6)

 

- 두번째 런타임 에러

그런데말입니다,, 여기는 코드트리였습니다,,

Traceback (most recent call last): File "Main.py", line 2, in <module> sys.setrecursionlimit(10**6) MemoryError

하하 뻐니

램 메모리가 부족해서 생기는 오류라고 합니다

 

해결 방법 : 깊이를 좀 더 얕게 설정해주면 됩니다

import sys
sys.setrecursionlimit(10**5)

성 공 .ᐟ .ᐟ .ᐟ

 

 

🔥 코드

import sys
sys.setrecursionlimit(10**5)

def dfs(x, y, k):
    for i in range(4):
        ni = x+di[i]
        nj = y+dj[i]

        if 0<= ni < n and 0 <= nj < m:
            if not visited[ni][nj] and ground[ni][nj] > k:
                visited[ni][nj] = True
                dfs(ni, nj, k)


n, m = map(int, input().split())
ground = [list(map(int, input().split())) for _ in range(n)]
max_k = max(ground)

di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

k = 1
safe_k = 1
safe = 0

while k < max(max_k):
    cnt = 0
    visited = [[False]*m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if not visited[i][j] and (ground[i][j] > k):
                visited[i][j] = True
                dfs(i, j, k)
                cnt += 1

    if cnt > safe:
        safe = cnt
        safe_k = k
    
    k += 1

print(f'{safe_k} {safe}')