문제
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.
마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.
성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.
우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.
입력
첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)
두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.
출력
용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.
만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.
예제 입력 1
6 6 16
0 0 0 0 1 1
0 0 0 0 0 2
1 1 1 0 1 0
0 0 0 0 0 0
0 1 1 1 1 1
0 0 0 0 0 0
예제 출력 1
10
🛡 백준 17836번 — 공주님을 구해라! (Python, BFS 풀이)
전설의 검 ‘그람’을 활용할 수 있는 독특한 BFS 문제다.
특히 칼을 얻은 뒤에는 벽을 무시하고 직선으로 갈 수 있다는 점이 시간 계산의 핵심이다.
이번 글에서는 내가 작성한 코드를 바탕으로 전체 풀이 과정을 정리한다.
1⃣ 문제 개요
성은 N x M 크기의 격자이며, 각 칸은 아래처럼 구성된다.
0: 빈 칸 (이동 가능)1: 벽 (칼 없이는 진입 불가)2: 전설의 검 ‘그람’ (먹으면 벽 무시 가능)
시작 위치는 (0, 0), 공주님은 (N-1, M-1)에 있다.
제한 시간 T 안에 도착하면 구출 성공, 아니면 "Fail".
핵심은:
✔ 그람 없이 공주님에게 가는 최단 시간
✔ 그람을 먹고 벽을 무시하며 가는 최단 시간
두 값 중 더 빠른 쪽을 선택해 T와 비교하면 된다.
2⃣ 접근 방식
① 맨해튼 거리로 사전 가지치기
최소로 움직여도 (N-1 + M-1)번 이동한다.
즉, 장애물이 없다고 가정해도 이 값이 T보다 크면 절대 도달 못 한다.
if (N-1 + M -1) > T:
print("Fail")
exit()
여기서 빠르게 컷해주면 이후 BFS 부담이 줄어든다.
② BFS 한 번으로 “두 가지 정보” 모두 구하기
내 BFS는 딱 한 번 돌린다:
직접 공주님까지 도달할 수 있는지
도중에 검(
2)을 만났을 때 시간 계산
검을 발견했을 때는:
검까지 걸린 시간 + 검 위치에서 공주까지의 맨해튼 거리
이렇게 계산하면 이후 벽을 무시할 수 있으므로
그 시점이 칼 루트 최단 시간 후보가 된다.
③ 최종적으로 비교할 값
visited[N-1][M-1]: 칼 없이 BFS로 직접 도착한 시간result_sword: 칼을 통해 계산된 최소 시간
둘 중 작은 값이 최종 후보다.
후보가 T 이하이면 출력, 아니면 "Fail".
3⃣ 시간 복잡도 분석
BFS는 각 칸을 최대 한 번씩 방문한다.
격자 크기:
N x M각 칸에서 네 방향 검사
따라서,
시간 복잡도: O(N × M)
공간 복잡도: O(N × M)
문제 최대 크기에서도 충분히 빠르게 해결된다.
4⃣ 로직 흐름(내 코드 기준 상세 해설)
이 부분은 실제 코드 흐름에 따라 순서대로 정리한다.
🔹 1단계 — 입력 및 기본 세팅
N, M, T = map(int,sys.stdin.readline().split())
maps = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
지도 정보를 그대로 2차원 배열로 받는다.
visited는 0으로 초기화(미방문 판단용).
🔹 2단계 — 맨해튼 거리 기반 빠른 실패 처리
if (N-1 + M -1) > T:
print("Fail")
exit()
절대 불가능한 경우 즉시 종료.
🔹 3단계 — BFS 준비
visited = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
방문 배열 0으로 초기화 (방문 여부 체크에 사용)
4방향 이동 정의
🔹 4단계 — BFS 수행
def bfs(coor_x, coor_y):
queue = deque()
queue.append([coor_x,coor_y])
visited[coor_x][coor_y] = 0
루트는 (0,0)에서 시작.
🔹 5단계 — BFS 확장 및 검 발견 처리
핵심 로직은 여기다.
if maps[nx][ny] == 2:
# 검까지 오는 데 걸린 시간 저장
visited[nx][ny] = visited[x][y] + 1
queue.append([nx,ny])
result_sword = visited[nx][ny] + (N - nx - 1) + (M - ny - 1)
칼을 발견하면 해당 위치까지 최소 시간이 확정된다.
이후 벽 무시 가능 → 공주까지 맨해튼 거리만 더하면 최단 시간.
그 외 빈칸은 그대로 이동하면서 BFS 탐색 유지.
🔹 6단계 — BFS 종료 후 결과 판정
조건별로 나누어:
공주에게 직접 도달한 경우
칼 경로로만 도달 가능한 경우
둘 다 가능한 경우
둘 다 불가능한 경우
각각 적절히 비교하여 T 이내인지 판정한다.
5⃣ 전체 코드 (내 코드 기반 정리본)
아래는 내가 작성했던 코드 흐름을 유지하면서,
블로그에 올리기 좋게 정리한 전체 코드다.
import sys
from collections import deque
N, M, T = map(int,sys.stdin.readline().split())
maps = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
# 맨해튼 거리 기반 컷
if (N-1 + M -1) > T:
print("Fail")
exit()
visited = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(coor_x, coor_y):
global visited
global T
global result_sword
queue = deque()
queue.append([coor_x,coor_y])
visited[coor_x][coor_y] = 0
while queue:
x, y = queue.popleft()
# 시간이 이미 T 초과하면 의미가 없음
if visited[x][y] > T:
return False
for i in range(4):
nx = x + dx[i]; ny = y + dy[i]
# 범위 + 미방문 체크
if 0<= nx < N and 0<= ny < M and not visited[nx][ny]:
# 칼 발견 시
if maps[nx][ny] == 2:
queue.append([nx,ny])
visited[nx][ny] = visited[x][y] + 1
result_sword = (
visited[nx][ny]
+ (N - nx - 1)
+ (M - ny - 1)
)
# 벽이 아니면 이동 가능
elif maps[nx][ny] != 1:
queue.append([nx,ny])
visited[nx][ny] = visited[x][y] + 1
result = 0
result_sword = 0
# BFS 실행
if not bfs(0,0):
# 공주에게 직접 못 갔고, 칼도 못 먹은 경우
if visited[N-1][M-1] == 0 and result_sword == 0 :
print("Fail")
exit()
# 칼로만 도달 가능한 경우
if visited[N-1][M-1] == 0 and result_sword != 0 :
if result_sword > T:
print("Fail")
exit()
print(result_sword)
# 둘 다 가능한 경우
if visited[N-1][M-1] != 0 and result_sword != 0:
print(min(visited[N-1][M-1], result_sword))
# 칼 없이만 가능한 경우
if visited[N-1][M-1] != 0 and result_sword == 0:
if visited[N-1][M-1] > T:
print("Fail")
exit()
else:
print(visited[N-1][M-1])
else:
# BFS는 끝났는데 결과가 시간 초과일 수 있음
if result_sword > T:
print("Fail")
else:
print(result_sword)
마무리
이 문제의 관건은 일반 BFS 거리와 칼을 통한 최단 거리 계산을 동시에 처리하는 구조다.
특히 칼을 먹은 뒤의 이동을 “맨해튼 거리”로 대체할 수 있다는 사실을
이해하면 풀이가 단순해진다.