1. 문제
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.
마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.
성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.
우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.
2. 입력
첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)
두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.
3. 출력
용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.
만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.
4. 예제 입력 / 출력
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
10
5. 풀이 과정
BFS로 찾은 경로는 최단 경로임을 보장받기 때문에 해당 문제는 BFS로 풀 수 있다. BFS로 찾은 경로가 왜 최단거리인지 알고 싶다면 여기를 참고해보면 된다.
from collections import deque
def bfs():
global answer, queue
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
# 방문 정보 초기화
visited = [[False] * m for _ in range(n)]
visited[0][0] = True
while queue:
count, x, y = queue.popleft()
# 공주님이 있는 칸에 도달한다면 count 값 반환
if x == m - 1 and y == n - 1:
return count
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 인덱스 범위를 벗어나거나 벽이 있는 칸, 방문한 칸으로는 못 움직임
if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[ny][nx] or field[ny][nx] == 1:
continue
queue.append((count + 1, nx, ny))
visited[ny][nx] = True
return t + 1 # 도달하지 않을 경우 t + 1을 반환해 Fail이 나오도록 함
n, m, t = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(n)]
queue = deque([(0, 0, 0)])
answer = bfs()
if answer <= t:
print(answer)
else:
print('Fail')문제가 단순히 (0, 0) 부터 (N, M)에 있는 공주님에 도달하는 최단시간을 구하는 것이었다면 다음과 같이 풀어볼 수 있다. 용사가 한 칸을 이동하는데 1시간이 걸리기 때문에 방문한 칸 수 = 걸린 시간 이라고 생각할 수 있다. queue에 몇 개의 칸을 방문했는지 나타내는 count 변수를 넣어줌으로써 공주님이 있는 곳에 방문한다면 해당 count 값을 반환시켜주면 된다.
하지만 위의 그림과 같이 그람을 얻고 벽을 부수고 나아가는 것이 더 시간이 적게 걸리는 경우도 있기 때문에
- 그람을 얻지 않고 벽을 우회해 공주님께 가는 경우
- 그람을 얻고 벽을 부수며 공주님께 가는 경우
두 가지 경우를 모두 고려해야 한다.
from collections import deque
# has_gram : 그람을 소유하고 있는지 여부
# go_to_gram : 그람이 있는 곳으로 이동하는지 여부, False라면 공주가 있는 곳으로 이동
def bfs(has_gram, go_to_gram):
global answer, queue
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
# 방문 정보 초기화
visited = [[False] * m for _ in range(n)]
visited[0][0] = True
while queue:
count, x, y = queue.popleft()
if go_to_gram:
# 그람을 발견한다면 해당 위치부터 다시 BFS 시행
if field[y][x] == 2:
queue = deque([(count, x, y)])
return bfs(True, False) # 그람을 가지고 있고, 공주님이 있는 곳으로 향함
else:
# 공주님이 있는 칸에 도달한다면 count 값 반환
if x == m - 1 and y == n - 1:
return count
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 인덱스 범위를 벗어나거나 방문한 칸으로는 못 움직임
if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[ny][nx]:
continue
# 그람을 가지고 있지 않은 경우 벽이 있는 칸으로는 못 움직임
if not has_gram and field[ny][nx] == 1:
continue
queue.append((count + 1, nx, ny))
visited[ny][nx] = True
return t + 1 # 도달하지 않을 경우 t + 1을 반환해 Fail이 나오도록 함
n, m, t = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(n)]
queue = deque([(0, 0, 0)])
route1 = bfs(False, False) # 그람을 거치지 않고 가는 루트
queue = deque([(0, 0, 0)])
route2 = bfs(False, True) # 그람을 거치고 가는 루트
answer = min(route1, route2)
if answer <= t:
print(answer)
else:
print('Fail')그람을 가지고 벽을 부수며 공주님께 가는 경우는 위와 같이 (0, 0)에서부터 그람까지의 최단 거리 + 그람의 위치에서 공주님까지의 최단 거리를 구하면 된다.
따라서 이 두 가지 경우 중 더 시간이 적게 걸리는 쪽을 출력해주면 된다.
6. 문제 링크
