[백준-17836] 공주님을 구해라! (Python)

문제링크 : https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

---

[풀이]

- 일반적인 BFS 문제와 똑같다고 생각했다.

- 하지만, 탐색하다가 그람을 찾으면 현 위치에서 공주가 있는(N - 1, M - 1) 과의 좌표 차이 값을 더하여 result에 추가했다.

- 공주가 있는 곳에 도착하면 현재 시간과 result의 최솟값을 저장하도록 하였고, 최종적으로 result가 T보다 크면 "Fail" 을 그렇지 않으면 최소 시간을 출력하도록 했다.

---

from collections import deque
n,m,T=map(int,input().split())
maps=[list(map(int, input().split())) for _ in range(n)]
visit=[[0 for _ in range(m)] for _ in range(n)]
q=deque()
q.append((0,0,0))
dx,dy=(-1,1,0,0),(0,0,-1,1)
result=float('inf')
while q:
    x,y,t=q.popleft()
    if x==n-1 and y==m-1:
        result=min(result,t)
        break
    if t+1>T : break
    for dir in range(4):
        nx,ny=x+dx[dir],y+dy[dir]
        if 0<=nx<n and 0<=ny<m and visit[nx][ny]==0:
            if maps[nx][ny]==1: continue
            elif maps[nx][ny]==0:
                visit[nx][ny]=True
                q.append((nx,ny,t+1))
            else:
                visit[nx][ny]=True
                tmp=t+1+abs(nx-(n-1))+abs(ny-(m-1))
                if tmp<=T:
                    result=tmp
if result>T:
    print("Fail")
else:
    print(result)​