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

💡문제접근

• 원점에서부터 시작하여 (N, M)에 도달하는데 걸리는 최단 시간을 구하는 문제다.
• 칼을 이용해서 벽을 부수면서 갈 수 있는 최단 시간과 칼을 찾지 않고 열린 길을 통해서 갈 수 있는 최단 시간을 구하고 두 최단 시간의 최솟값을 출력하면 된다.

💡코드(메모리 : 34176KB, 시간 : 84ms)

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

N, M, T = map(int, input().strip().split())
castle = [list(map(int, input().strip().split())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
result = 100000

def BFS():
    global result
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = 1
    while queue:
        x, y = queue.popleft()
        # 만약 칼이 있다면? → (0, 0)부터 칼이 있는 지점까지 도달하는데 걸리는 시간에 칼이 있는 지점에서부터 공주님이 있는 지점까지 도달하는데 걸리는 시간
        if castle[x][y] == 2:
            result = N-1-x + M-1-y + visited[x][y] - 1
        if x == N-1 and y == M-1:
            return min(result, visited[x][y] - 1)
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if 0 <= nx < N and 0 <= ny < M and castle[nx][ny] != 1:
                if visited[nx][ny] == 0:
                    queue.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
    return result

val = BFS()
if val > T:
    print("Fail")
else:
    print(val)

💡소요시간 : 27m