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

17836번 : 공주님을 구해라!

예외처리를 잘 못 해 애를 먹었던 문제이다.

검을 찾지 않고 바로 공주에게 가는 경우의 시간, 검을 찾고 공주에게 가는 경우의 시간 두 가지를 구하면 된다.

검을 잡은 경우 모든 벽을 부술 수 있기 때문에 검까지 가는데 걸리는 시간만 구해놓으면

검을 들고 공주에게 가는 경우의 시간은 좌표계산을 통해 구할 수 있다.

결국 검을 찾지 않고 바로 공주에게 가는 경우만 계산하면 된다.

이 때, 네 가지 상황이 발생 할 수 있다.

1. 검과 공주 둘 다 갈 수 없는 경우
2. 검에게만 갈 수 있는 경우
3. 공주에게만 갈 수 있는 경우
4. 둘 다 갈 수 있는 경우

1번은 바로 Fail 을 반환하고 2, 3, 4번은 문제에서 주어진 시간제한 안에 도착하는지 여부를 판단 후 반환하면 된다.

---

import sys
from collections import deque


def BFS(field, sword):
    sword_time = -1
    dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    queue = deque([(0, 0, 0)])
    field[0][0] = 1

    while queue:
        now_i, now_j, time = queue.popleft()
        if (now_i, now_j) == sword:
            sword_time = time
        for value in dirs:
            visit_i, visit_j = now_i + value[0], now_j + value[1]
            if 0 <= visit_i < N and 0 <= visit_j < M and field[visit_i][visit_j] < 1:
                field[visit_i][visit_j] = time + 1
                queue.append((visit_i, visit_j, time + 1))

    return sword_time


def solution(field):
    sword = ()
    for i in range(N):
        for j in range(M):
            if field[i][j] == 2:
                field[i][j] = 0
                sword = (i, j)

    sword_time = BFS(field, sword)
    direct = field[N - 1][M - 1]
    if sword_time >= 0:
        sword_time += (N - 1) - sword[0] + (M - 1) - sword[1]

    # 검과 공주 둘 다 갈 수 없는 경우
    if direct == 0 and sword_time == -1:
        return "Fail"

    # 검에만 갈 수 있는 경우
    if direct == 0 and sword_time != -1:
        if sword_time <= limit:
            return sword_time
        else:
            return "Fail"

    # 공주에게만 갈 수 있는 경우
    if direct and sword_time == -1:
        if direct <= limit:
            return direct
        else:
            return "Fail"

    # 검과 공주 둘 다 갈 수 있는 경우
    answer = min(direct, sword_time)
    if answer <= limit:
        return answer
    else:
        return "Fail"


if __name__ == "__main__":
    N, M, limit = map(int, input().split())
    field = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(N)]

    print(solution(field))