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

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

17836번: 공주님을 구해라!

bfs 문제인데 칼이라는 조건이 추가되었다 
칼이 있을 때와 칼이 없을 때 최단거리가 달라진다 ..!!!! 

이걸 어떻게 처리하느냐가 관건인데, 우선 칼을 가지고 있으면 굉장히 문제가 간단해진다 

if array[x][y] == 2: # knife
    min_time = visited[x][y]-1 + n-1-x + m-1-y # 칼까지의 최단거리 + 칼에서부터 공주까지 거리

칼까지의 최단거리 + 칼에서 공주님 위치까지의 거리 
를 구하면 되는데, 칼에서 공주님 위치까지의 거리는 어처피 한칸씩 이동만 하면 된다. 

# 17836 공주님을 구해라 !
from collections import deque

n, m, t = map(int, input().split())
array = []
# 상하좌우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    array.append(list(map(int, input().split())))

def bfs():
    queue = deque()
    queue.append((0, 0)) # x, y, time, knife
    visited = [[0]*m for _ in range(n)]
    visited[0][0] = 1
    min_time = 1000000
    while queue:
        x, y = queue.popleft()
        if x == n-1 and y == m-1:
            min_time = min(min_time, visited[-1][-1]-1)
            return min_time
        if array[x][y] == 2: # knife
            min_time = visited[x][y]-1 + n-1-x + m-1-y # 칼까지의 최단거리 + 칼에서부터 공주까지 거리
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
                if array[nx][ny] != 1:
                    queue.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
    return min_time

result = bfs()
if result > t:
    print("Fail")
else:
    print(result)