[백준 17090번] 미로 탈출하기(파이썬)

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

17090번: 미로 탈출하기

단순하게 각 좌표마다

bfs를 써서

이동한 다음에

미로를 빠져나가는지 확인하는 방식이 있지만

이 방식은 제출하자마자 시간초과가 뜹니다.

이 문제가 골드3인걸 생각하면

그렇게 단순할리가 없죠.

 

이 문제는 dp를 함께 사용하는 방식입니다.

dp라고 해봤자, 해당 지점의 탈출여부를 판단하는 건데요.

만약에 위로 이동했을 때 좌표가

'나갈 수 있는 좌표'라는 표시가 있다면

굳이 더 나아가지 않아도

'나갈 수 있다'라는 걸 알 수 있습니다.

그러니 그걸 체크해주는 리스트를 만들고

그걸 이용해서 판단하면 됩니다.

#백준 17080번 미로탈출하기
import sys
sys.setrecursionlimit(10**5+300000)

dx=[-1,0,1,0]
dy=[0,1,0,-1]
N,M=map(int,input().split())
room=[[-1]*M for _ in range(N)]
check=[[-1]*M for _ in range(N)]
for i in range(N):
    tmp=input().rstrip()
    for j in range(M):
        if tmp[j]=='U':
            room[i][j]=0
        elif tmp[j]=='R':
            room[i][j]=1
        elif tmp[j]=='D':
            room[i][j]=2
        elif tmp[j]=='L':
            room[i][j]=3

def dfs(x,y):

    go=room[x][y]
    nx=x+dx[go]
    ny=y+dy[go]
    #미로를 벗어나면 1을 반환
    if nx<0 or nx>=N or ny<0 or ny>=M:
        return True
    #해당 지점에서 나갈 수 있는지 없는지 여부가 판단되면 그 값을 반환
    #나갈 수 있는 곳으로 가면 자연스럽게 나갈 수 있음
    if check[nx][ny]>=0:
        return check[nx][ny]
    #아직 탐색이 안된 지역이라면
    if check[nx][ny]==-1:
        check[nx][ny]=-2
        check[nx][ny]=dfs(nx,ny)
        return check[nx][ny]
    return 0
cnt=0
for x in range(N):
    for y in range(M):
        check[x][y]=dfs(x,y)
        cnt+=check[x][y]

print(cnt)

이 문제는 dfs를 써야하더군요.

bfs를 쓰면 시간초과가 나버려서 안됩니다.

dfs로 쓸때는

재귀제한을 걸어놔야지

메모리초과,recursion error가 안뜹니다.

이런 달갑지 않지만

그래도 bfs,dfs를 사용할 때

dp를 함께 쓸 수 있는 방법을 익힐 수 있는 좋은 문제입니다.