백준 #17836 공주님을 구해라!

코드

import sys, math
# sys.stdin = open("input.txt")
from collections import deque
input = sys.stdin.readline


def solve():
    global s_time, t
    q = deque()
    q.append((0, 0, 0))
    visited[0][0] = True
    while q:
        r, c, time = q.popleft()
        if arr[r][c] == 2:
            s_time = time + abs(r - n + 1) + abs(c - m + 1)
        if r == n - 1 and c == m - 1:
            return time if time <= t else False

        for k in range(4):
            nr, nc = r + dr[k], c + dc[k]
            if nr < 0 or nr >= n or nc < 0 or nc >= m:
                continue
            if not visited[nr][nc] and arr[nr][nc] != 1:
                visited[nr][nc] = True
                q.append((nr, nc, time + 1))

    return False

n, m, t = map(int, input().rstrip().split())
arr = [list(map(int, input().rstrip().split())) for _ in range(n)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
visited = [[False] * m for _ in range(n)]
s_time = 10001
time = solve()
if time:
    print(min(time, s_time))
else:
    if s_time <= t:
        print(s_time)
    else:
        print("Fail")

풀이

처음에 시도했을 때 검까지 있는 곳을 구하고 bfs를 두번 돌리려고 했었다.

그런데 코드가 너무 길어지고 지저분해보여서 고민하다가 어차피 검을 얻으면 모든 벽을 부술 수 있기 때문에

공주와의 거리는 검까지의 거리 + 검으로 부터 공주까지의 맨해튼 거리가 된다.

공주를 찾아야하는 최소 시간이 있는데 계속 고려를 안해줘서 많이 틀렸었다 ㅎㅎ

문제를 잘 읽자!! 화이팅!