백준 17836 공주님을 구해라!

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m, t = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(m):
        if g[i][j] == 2:
            gx, gy = i, j
            break

def bfs(u, v, gram):
    q = deque()
    check = [[-1] * m for _ in range(n)]
    q.append((u, v))
    check[u][v] = 0
    if gram:
        while q:
            x, y = q.popleft()
            for dir in range(4):
                nx, ny = x + dx[dir], y + dy[dir]
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if check[nx][ny] == -1:
                    q.append((nx, ny))
                    check[nx][ny] = check[x][y] + 1
    else:
        while q:
            x, y = q.popleft()
            for dir in range(4):
                nx, ny = x + dx[dir], y + dy[dir]
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if check[nx][ny] == -1 and g[nx][ny] != 1:
                    q.append((nx, ny))
                    check[nx][ny] = check[x][y] + 1
    return check

ans = 101 * 101
# 그냥 가는 경우
nogram = bfs(0, 0, 0)
# 도착할 수 있는 경우
if nogram[n-1][m-1] != -1:
    ans = min(ans, nogram[n-1][m-1])
# 그람
# 그람을 가지러 갈 수 있는 경우
if nogram[gx][gy] != -1:
    yesgram = bfs(gx, gy, 1)
    ans = min(ans, nogram[gx][gy] + yesgram[n-1][m-1])

if ans > t:
    print("Fail")
else:
    print(ans)

bfs를 <1. 그람이 없는 경우 2. 그람이 있는 경우> 두번 돌렸고 나눠서 코드 짬
1. 그람이 없는 경우 : 공주님에게 도착할 수 있는 경우만 최소값 연산
2. 그람이 있는 경우 : 없을 때 그람까지의 거리 + 있을 때 그람 ~ 공주까지의 거리. 이 연산은 그람을 가지러갈 수 없는 경우 (막혀있는 경우)에는 실행하지 않는다.