[백준/BOJ]#13565:침투[DFS/그래프/깊이우선탐색/파이썬/python]

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

13565번: 침투

메모리 초과의 늪에서 못 빠져나오게 한 문제,,, 대체 코드에 문제가 없는데 왜 이러는건가 재귀탐색제한을 줄여도 보고 30분을 헤매었는데,, 결국 컴파일러를 pypy3가 아닌 python3 으로 바꾸니 통과했다;;;

백준에서 이런 경우가 간혹 있는데 이럴때마다 시간이 아깝고 힘 빠진다^^;; 승부는 내야하니 정답은 내야겠고,,

 

 

 

bfs보다는 dfs로 푸는 게 더 적합하다고 판단했다. 맨 마지막 줄에 닿으면 종료조건을 걸면 된다. 

 

m,n이 행 열로 입력을 받으므로 dfs함수의 인자는 y, x이다. 

#13565_침투
import sys
sys.setrecursionlimit(10**9)

        
#visited = [[-1 for _ in range(n)] for _ in range(m)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]
ans=False
def dfs(y,x):
    global ans
    
    if y == m-1:
        ans = True
        return True

    elect[y][x]=2
    for i in range(4):
        tx = x + dx[i]
        ty = y + dy[i]
        if 0<=ty<m and 0<=tx<n and elect[ty][tx]==0:
            dfs(ty, tx)
            
        
    

m, n = map(int,input().split())
elect=[]
for _ in range(m):
    elect.append(list(map(int,input())))
for i in range(n):
    if elect[0][i]==0:
        dfs(0,i)
        if ans:
            print('YES')
            break
if not ans:
    print('NO')