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

공주님을 구해라! 문제 바로 가기

풀이 날짜: 2026-03-19

baekjoon 알고리즘 문제 풀이

풀이 코드


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

n,m,t = map(int, input().split())
visited = [[False] * m for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(n)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

q = deque()
q.append((0,0,0))
visited[0][0] = True
answer = int(1e9)

while q:
    x,y,time = q.popleft()
    if time > t:
        continue

    if x == n-1 and y == m-1:
        answer = min(answer, time)

    if graph[x][y] == 2:
        dist = (n-1-x) + (m-1-y)
        answer = min(answer, time+dist)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<n and 0<=ny<m:
            if not visited[nx][ny] and graph[nx][ny] != 1:
                visited[nx][ny] = True
                q.append((nx,ny,time+1))
if answer <= t:
    print(answer)
else:
    print("Fail")

접근 방법

제한 시간 내에 성을 탐색하여 공주가 있는 위치까지 도달하는 최소 시간을 구하는 문제이다. 맵은 2차원 격자로 주어지며, 빈 칸(0), 벽(1), 검(2)으로 구성되어 있다. 시작 위치는 (0,0), 도착 위치는 (n-1,m-1)이며, 벽은 통과할 수 없지만 검을 획득하면 벽을 무시하고 이동할 수 있다. 따라서 단순한 최단 거리 탐색이 아니라, ‘검을 획득하는 경우’까지 고려해야 하는 문제이다.

문제 핵심 아이디어

이 문제의 핵심은 두 가지 경로를 동시에 고려하는 것이다. 첫 번째는 검 없이 BFS를 통해 공주까지 도달하는 경로이고, 두 번째는 중간에 검을 획득한 후 벽을 무시하고 공주까지 직선으로 이동하는 경로이다. 특히 검을 획득한 이후에는 더 이상 BFS 탐색이 필요 없고, 공주까지의 최단 거리를 맨해튼 거리로 계산할 수 있다는 점이 중요한 포인트이다.

BFS를 사용하는 이유

이 문제는 “최단 시간”을 구하는 문제이므로 DFS가 아닌 BFS를 사용해야 한다. BFS는 가까운 거리부터 순차적으로 탐색하기 때문에, 특정 위치에 처음 도달했을 때의 시간이 곧 최단 시간이다.

구현 방식

큐에는 (x, y, time) 형태로 현재 위치와 도달 시간을 함께 저장한다. BFS를 진행하면서 현재 위치가 공주 위치라면 정답 후보를 갱신하고, 검을 발견한 경우에는 현재까지 걸린 시간에 공주까지의 맨해튼 거리를 더해 또 하나의 후보를 만든다. 이후 상하좌우로 이동하면서 방문하지 않았고 벽이 아닌 칸만 큐에 추가하여 탐색을 이어간다.

검 처리 방식

검이 있는 위치에 도달하면 이후에는 벽을 무시할 수 있기 때문에, 굳이 BFS로 계속 탐색할 필요 없이 바로 공주까지의 거리를 계산한다. 이때 사용하는 공식은 (n-1 - x) + (m-1 - y)이며, 이는 현재 위치에서 목표 위치까지의 최단 이동 횟수(맨해튼 거리)를 의미한다. 따라서 전체 시간은 현재까지의 시간 + 남은 거리로 계산할 수 있다.

내가 헷갈렸던 부분

DFS는 최단 거리를 보장하지 않기 때문에 이 문제에 적합하지 않다. 또한, 검을 획득한 이후에도 BFS를 계속 돌리는 경우가 있는데, 이는 비효율적이며 시간 초과의 원인이 될 수 있다. 검을 얻는 순간에는 반드시 거리 계산으로 처리해야 한다.

Vienna sausage