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

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

17836번: 공주님을 구해라!

 용사는 마왕성에서 공주를 구해야한다. 마왕성은 1x1 크기의 정사각형으로 이뤄져있고, 각 칸은 이동할 수 있는 길 또는 벽이다. 용사는 인접 칸으로 이동하기 위해서 1시간이 걸리고 주어진 시간 내에 공주에게 도달해야한다. 마왕성 어딘가에는 용사의 무기 "그람"이 1개 존재하는데, 이 그람을 가지면 그 순간부터 벽을 부수고 지나갈 수 있다. 용사가 공주를 구할 수 있는지 여부를 확인하고, 구할 수 있다면 가장 빠른 시간을 구하는 문제이다.

 

 BFS 탐색을 통해 길을 따라 이동하면서 다니는 길마다 걸리는 최소 시간을 계산한다. 출발점으로부터 가까운 길을 먼저 찾기 때문에 공주가 있는 곳에 도달했을 때 걸린 시간이 곧 최소 시간이다. 단, 탐색 도중 그람을 찾게되면 벽을 무시하고 지나갈 수 있기 때문에 그람이 있던 위치를 시작으로 공주가 있는 곳 까지의 그래프 탐색을 또 진행해서 계산된 시간과 비교해봐야한다.

 

 유의해야할 사항들이 몇가지 있다. 보통의 방법으로 길을 따라 공주에게 갈 수 없는 경우 공주의 위치까지 걸리는 시간은 0이다. 만약 그럴 경우(걸리는 시간이 0인 경우), 그람을 갖고 공주에게 가는 시간과 비교하면 둘 중 최솟값은 0이 되므로 공주에게 도달할 수 없다고 판단해버리지 않도록 해야한다. 또한 그람을 갖고 공주에게 가기 위해선, 길을 따라서 그람이 있는 곳 까지 도달할 수 있어야 함을 잊지말자.

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

def bfs(c,s,value,gram):
    dx, dy = [1,0,-1,0], [0,1,0,-1]
    gx, gy = 0, 0
    gf = 0
    v = [[False]*m for _ in range(n)]
    t = [[0]*m for _ in range(n)]

    a, b = s
    queue = deque([s])
    v[a][b], t[a][b] = True, value
    
    while queue:
        x, y = queue.popleft()
        if c[x][y] == 2:
            gx, gy = x, y
            gf = 1
        for i in range(4):
            px, py = x+dx[i], y+dy[i]
            if px < 0 or px > n-1 or py < 0 or py > m-1:
                continue
            if not v[px][py]:
                if c[px][py] != 1 or (c[px][py] == 1 and gram):
                    queue.append((px,py))
                    v[px][py] = True
                    t[px][py] = t[x][y] + 1
    return t[n-1][m-1], (gx, gy), t[gx][gy], gf

n, m, l = map(int, input().split())
castle = [list(map(int, input().split())) for _ in range(n)]
r1, gp, gv, gf = bfs(castle, (0, 0), 0, 0)
if gf:
    r2 = bfs(castle, gp, gv, 1)[0]
    if r1 > 0: r = min(r1, r2)
    else: r = r2
else:
    r = r1

if r > l or r == 0:
    r = 'Fail'
print(r)