[BOJ/백준] 안전영역 2466 silver1/DFS, BFS 풀이 / Python Recursion ERROR

✨ 문제

https://www.acmicpc.net/problem/2468

✨ DFS 풀이

import sys
sys.setrecursionlimit(100000)

n=int(input())
graph=[]
for _ in range(n):
    temp=list(map(int,sys.stdin.readline().strip().split()))
    graph.append(temp)


max_height=max(map(max,graph))



def dfs(x,y,graph,num):
    if 0 > x or x > n-1 or y < 0 or  y > n-1:
        return
    if visited[x][y] or graph[x][y]<=num:
        return
    visited[x][y]=True
    global area
    area+=1
    dfs(x+1,y,graph,num)
    dfs(x,y+1,graph,num)
    dfs(x-1,y,graph,num)
    dfs(x,y-1,graph,num)
    return True


ans_list=[]
for i in range(max_height):
    ans = 0
    visited=[[False]*n for _ in range(n)]

    for r in range(n):
        for c in range(n):
            area=0
            dfs(r,c,graph,i)
            if area>=1:
                ans+=1
    ans_list.append(ans)

if len(ans_list)>0:
    print(max(ans_list))
else:
    print(0)

처음엔 DFS 재귀형태로 풀었는데 채점되는 속도가 느리긴 하지만 풀리긴 한다...! recursion error도 났었는데 아래와 같은 방법으로 해결했다.

✨ Python Recursion ERROR

원래 파이썬에서는 1000번 이상의 recursion이 발생하면 recursion error 가 뜬다고 한다!!

import sys
sys.setrecursionlimit(100000)

나는 위의 코드를 추가해서 해결했다.

✨ BFS 풀이

from collections import deque
import sys

graph=[]
n=int(input())
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().strip().split())))

max_num=max(map(max,graph))
dx=[0,0,-1,1]
dy=[1,-1,0,0]

def bfs(curr_x,curr_y,visited,h):

    queue=deque([[curr_x,curr_y]])
    global area
    area=0
    while queue:
        x,y=queue.popleft()
        if x<0 or x>n-1 or y<0 or y>n-1:
            continue
        curr_n=graph[x][y]
        if curr_n>h:
            area+=1
            if not visited[x][y]:
                visited[x][y] = True
                for x_move,y_move in zip(dx,dy):
                    queue.append((x+x_move,y+y_move))

ans=[]
for h in range(max_num):
    visited=[[False]*n for _ in range(n)]
    cnt=0
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                bfs(i,j,visited,h)
                if area>0:
                    cnt+=1
    ans.append(cnt)

if len(ans)>0:
    print(max(ans))
else:
    print(0)

DFS로 문제가 풀리긴했지만 재귀로 dfs로 호출하는 과정에서 print 문으로 내부적으로 어떻게 호출이 되나 보니까 이미 이전에 방문한 구역을 재방문하는 걸 발견했다. 😂😭 이상하다 난 분명히 visited 처리를 했는데..?라는 생각이 들었다.. 근데 잘 생각해보니 dfs를 여러번 재호출 하는거라 내가 의도한 대로 동작하는데에는 한계가 있다고 생각했고!!
큐를 사용해서 선입선출로 탐색한 위치를 제어가능 하도록 bfs로 개선해서 풀어야겠다고 생각했다~!!

BFS로 다시 코드를 작성하고 채점하니 DFS로 풀었을 때 보다 훨씬 빠른 속도로 채점되는걸 확인할 수 있었다 😭💖

ㅠㅠ!! 8트만에 성공 ~ 중꺾마! 파이팅 😀👊