백준 17836 공주님을 구해라! python

17836번: 공주님을 구해라!

문제

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (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"을 출력한다.

풀이

검을 획득하면 벽을 무한히 부수고 이동할 수 있다고 하여 바로 공주에게 가는 방법과 검을 찾게 된 순간 공주의 위치까지 떨어진 거리를 구하여 비교하여주고 두 조건중 시간 제한 안에 통과되는 조건이 있을 시에만 걸린 시간을 출력해주고 아닐 경우 'Fail'을 출력해 주었습니다.

from collections import deque
n, m, t = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
# 영역의 크기와 지도를 받아줍니다.
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 4방향 탐색을 정의합니다.

def gram(a, b):
    # 검을 찾아 걸리는 시간을 확인하는 함수입니다.
    global t
    q = deque()
    q.append((a, b, 0))
    visited = [[0]*m for _ in range(n)]
    visited[a][b] = 1
    # q라는 이름으로 덱을 만들어주고 영역의 크기와 같은 방문처리할 리스트를 만들어줍니다.
    while q:
        x, y, cnt = q.popleft()
        if maps[x][y] == 2:
            return cnt + (n + m - x - y - 2)
        # 검의 위치에 도달하였다면 검의 위치까지 걸리는 시간에 공주의 x, y 좌표에서 검의 x, y 좌표를
        # 빼준값을 더해줍니다.
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx in range(n) and ny in range(m):
                if maps[nx][ny] != 1 and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx, ny, cnt + 1))
                    # 4방향 탐색을 통해 방문한적이 없고 벽이 아니라면 1의 시간이 더 걸린다고 표시하여 방문처리합니다.
    return t + 1
    # 검의 위치에 도달하지 못했다면 제한 시간 밖의 수를 돌려줍니다

def princess(a, b):
    # 공주 위치까지 바로 이동하는 함수입니다.
    global t
    q = deque()
    q.append((a, b, 0))
    visited = [[0]*m for _ in range(n)]
    visited[a][b] = 1
    # q라는 이름으로 덱을 만들어주고 영역의 크기와 같은 방문처리할 리스트를 만들어줍니다.
    while q:
        x, y, cnt = q.popleft()
        if x == n - 1 and y == m - 1:
            return cnt
        # 공주의 위치에 도착했으면 걸린 시간을 반환해줍니다.
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx in range(n) and ny in range(m):
                if maps[nx][ny] != 1 and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx, ny, cnt + 1))
                    # 4방위 탐색을 통해 영역의 크기 안에있고
                    # 벽이 아니고 방문한 적이 없으면 방문 처리를 해주고
                    # q에 시간이 1만큼 더 들었다는 표시와 함께 q에 넣어줍니다.
    return t + 1
    # q에 값이 없는데 공주에게 도달하지 못했다면 제한시간보다 큰 숫자를 돌려줍니다.

p = princess(0, 0)
g = gram(0, 0)
result = min(p, g)
# 검을 찾고 공주에 도달하는 방법과 바로 도달하는 방법중 작은 수를 결과로 설정하고
if result <= t:
    print(result)
    # 제한시간 안이라면 값을 출력해주고
else:
    print('Fail')
    # 제한시간보다 더 걸린다면 'Fail'을 출력해줍니다.