17836번 공주님을 구해라!

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

---

아이디어

처음에는 검을 찾았는지 확인하는 flag 변수를 활용해 flag가 True라면 벽이어도 그냥 간다고 생각해서 코드를 복잡하게 짰었다. 근데 그렇게 하게 되면 값을 계속 덮어쓰면서 같은 곳을 몇 번이나 돌게 된다.

검을 찾으면 검의 위치부터 공주가 있는 위치의 최단거리는 바로 구할 수 있다.(벽이어도 뚫으므로)
하지만 검을 찾았다고 바로 이 최단거리를 리턴해버리면 검을 안 찾고 빨리 갈 수 있는 경우 틀리다고 나온다.
그래서 검을 찾았을 땐 이 값을 저장해두고 있다가 목적지(공주 위치)에 도달했을 때 값을 비교하여 리턴
또는 queue가 empty가 될 때까지 돌았는데 목적지에 도달하지 못했을 때 검을 찾아 최단거리를 저장해두었다면 리턴, 아니면 T보다 큰 수 리턴(Fail이므로)

---

코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    queue = deque([(0, 0)])
    gramTime = 0
    
    while queue:
        x, y = queue.popleft()
        if (x, y) == (N-1, M-1): # 목적지 도달
            if gramTime: # 검 찾았다면
                return min(visited[x][y], gramTime)
            return visited[x][y]

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M: continue # 성 벗어남
            if castle[nx][ny] == 1 or visited[nx][ny] > -1: continue # 벽이거나 이미 방문
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx, ny))
            if castle[nx][ny] == 2:  # 검 찾으면 최단거리 저장
                gramTime = visited[nx][ny] + (N - 1 - nx) + (M - 1 - ny)

    if gramTime:
        return gramTime
    return T+1

N, M, T = map(int, input().split())
castle = [list(map(int, input().split())) for _ in range(N)]
visited = [[-1]*M for _ in range(N)]
visited[0][0] = 0
dx = [1, -1, 0, 0] # 하상좌우
dy = [0, 0, -1, 1]
result = bfs()
if result <= T:
    print(result)
else:
    print("Fail")