문제
영웅은 악마가 숨은 공주를 구해야 합니다.N, 중) 크기 (1,1)의 성 입구로. 마왕은 영웅이 공주를 찾지 못하도록 성의 여러 곳에 마법의 벽을 세웠습니다. 영웅은 현재 무기로는 마법의 벽을 통과할 수 없으며 마법의 벽을 피합니다(N, 중) 그 자리에 공주님을 구해야 합니다.
마왕은 영웅을 괴롭히기 위해 공주를 저주했습니다. 저주받은 공주 티제 시간에 영웅을 만나지 못하면 영원히 돌로 변할 것입니다. 공주를 구출하고 청혼하려는 영웅은 반드시 티시간 안에 공주가 있는 곳에 도달해야 합니다. 영웅이 한 칸 이동하는 데 1시간이 걸립니다. 바로 공주가 있는 곳 티구원은 때가 와도 가능합니다. 영웅은 위, 아래, 왼쪽 및 오른쪽으로 이동할 수 있습니다.
성 안에는 선대 영웅이 사용했던 전설의 검 ‘그람’이 숨겨져 있다. 영웅이 그람을 구하면 마법의 벽이 있는 감방이라도 즉시 벽을 뚫고 그 광장으로 갈 수 있다. “그람”은 성 어딘가에 항상 존재하며 영웅은 그람이 있는 곳에 도착하면 사용할 수 있습니다. 그람이 뚫을 수 있는 벽의 수에는 제한이 없습니다.
영웅이 공주를 안전하게 구할 수 있는지, 그렇다면 얼마나 빨리 구할 수 있는지 봅시다.
기입
첫 번째 줄에는 성의 크기인 N과 M, 그리고 공주에 대한 저주 시간 제한인 정수 T가 포함됩니다. 첫 번째 줄의 세 숫자는 공백으로 구분됩니다. (3≤N, M≤100, 1≤T≤10000)
두 번째 줄부터 N+1 줄까지 성의 구조를 나타내는 M개의 숫자가 공백으로 구분되어 제공됩니다. 0은 빈 사각형, 1은 마법의 벽, 2는 그람이 놓인 사각형입니다. (1,1) 및 (N,M)은 0입니다.
누르다
영웅이 제한 시간 T 내에 공주에게 도달할 수 있는 경우 공주에게 도달하는 최단 시간이 주어집니다.
영웅이 T 시간 내에 공주를 구하지 못하면 “실패”가 반환됩니다.
샘플 입력 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
샘플 입력 2
3 4 100
0 0 0 0
1 1 1 1
0 0 2 0
샘플 출력 2
Fail
설명
from collections import deque
N, M, T = map(int, input().split()) # N: 세로, M: 가로, T: 제한 시간
graph = (list(map(int, input().split())) for _ in range(N)) # 성의 지도
visit = ((0) * M for _ in range(N)) # 방문 처리를 위한 리스트
def bfs(): # 너비우선탐색
gram = 10001 # (0, 0)에서 검이 있는 곳 까지 도달하는 시간
queue = deque(((0, 0))) # 시작 좌표를 큐에 넣는다
visit(0)(0) = 1 # 시작 좌표 방문처리
dx = (-1, 1, 0, 0) # 상, 하, 좌, 우
dy = (0, 0, -1, 1)
while queue: # 큐가 비어있지 않으면 반복
x, y = queue.popleft() # 좌표 할당
if (x, y) == (N - 1, M - 1): # x, y가 공주님이 있는 좌표와 동일하면
return min(visit(x)(y) - 1, gram) # 더 적게 걸린 시간 반환
if graph(x)(y) == 2: # x, y 좌표에 검이 있으면
gram = visit(x)(y) - 1 + N - 1 - x + M - 1 - y
# 검이 있는 곳에 도달하기 까지 걸린 시간
# + 검이 있는 좌표에서 공주님이 있는 좌표까지 가는 데 걸리는 시간
for k in range(4): # 사방탐색
nx = x + dx(k)
ny = y + dy(k)
# 성의 범위를 벗어나지 않으면서 방문하지 않은 곳이면
if 0 <= nx < N and 0 <= ny < M and not visit(nx)(ny):
if graph(nx)(ny) == 0 or graph(nx)(ny) == 2: # 값이 0 또는 2이면
visit(nx)(ny) = visit(x)(y) + 1
# 시작 좌표에서 이전 좌표까지 방문하는 데에 걸린 시간 + 1을
# 해당 좌표 값에 넣어준다
queue.append((nx, ny)) # 큐에 넣어준다
return gram # 조건문을 거치지 않고 함수가 끝난다면 gram을 그대로 반환
result = bfs() # 함수 호출
if result > T: # 제한 시간보다 결과가 크게나왔다면
print('Fail') # 실패
else:
print(result) # 시간을 출력한다No.17836: 공주를 구하라!
주인공은 악마에게 숨은 공주를 구하기 위해 (N,M) 큰 성의 입구(1,1)로 들어갔다. 마왕은 영웅이 공주를 찾지 못하도록 성의 여러 곳에 마법의 벽을 세웠습니다. 전사에게는 현재가 있다
www.acmicpc.net