[백준] 19238번 : 스타트 택시 (파이썬, Python)

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

문제

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

 

<그림 1>

<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.

<그림 2>

<그림 3>

<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.

<그림 4>

<그림 5>

<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.

<그림 6>

<그림 7>

<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

코드

from collections import deque

n, m, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
startx, starty = map(int, input().split())
sx, sy = startx-1, starty-1
person = []

for i in range(2, m+2):
    psx, psy, pex, pey = map(int, input().split())
    person.append((psx-1, psy-1, pex-1, pey-1))
    # 손님이 존재하는 자리는 2로 저장
    graph[psx-1][psy-1] = 2


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

# 손님 태우러 가기
def bfs(x, y):
    Q = deque()
    Q.append((x, y))
    visit = [[0] * n for _ in range(n)]
    visit[x][y] = 1
    distance = [[0]*n for _ in range(n)]
    temp = []
    while Q:
        x, y = Q.popleft()
        if graph[x][y] == 2:
            temp.append((x, y, distance[x][y]))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != 1 and visit[nx][ny] == 0:
                visit[nx][ny] = 1
                distance[nx][ny] = distance[x][y] + 1
                Q.append((nx, ny))
    return sorted(temp, key=lambda x:(-x[2], -x[0], -x[1]))

# 손님 목적지까지 가기, 목적지까지 갈 수 있으면 위치랑 거리 저장 아니면 False 리턴
def go_destination(x, y, destx, desty):
    Q = deque()
    Q.append((x, y))
    visit = [[0] * n for _ in range(n)]
    visit[x][y] = 1
    distance = [[0] * n for _ in range(n)]
    temp = []
    while Q:
        x, y = Q.popleft()
        if x == destx and y == desty:
            temp.append((x, y, distance[x][y]))
            return temp

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != 1 and visit[nx][ny] == 0:
                visit[nx][ny] = 1
                distance[nx][ny] = distance[x][y] + 1
                Q.append((nx, ny))
    return False

# 모든 승객을 태울 수 있으면 Flag = True 아니면 Flag = False
flag = True
while True:
    tmp = bfs(sx, sy)
    
    # human : 현재 승객이 존재하면 True 아니면 False
    human = False
    
    # 승객의 목적지
    destx, desty = 0, 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 1:
                human = True
                
    # 만약에 태운 승객이 존재하지 않으면 반복문 탈출 이 때 만약 승객이 존재하면 flag = False
    if len(tmp) == 0:
        if human == True:
            flag = False
        break
        
    # 가장 가까운 승객을 태운 위치와 거리
    newx, newy, dist = tmp.pop()
    
    # 그 승객의 목적지 저장
    for i in person:
        if i[0] == newx and i[1] == newy:
            destx, desty = i[2], i[3]
            
    # 현재 승객을 태웠으므로 빈 공간으로 바꿈
    graph[newx][newy] = 0
    
    # 승객을 태우러 간 거리만큼 연료 뺌
    k -= dist
    
    # 만약 연료가 0이하면 flag= False하고 반복문 탈출
    if k < 0:
        flag = False
        break
    new_temp = go_destination(newx, newy, destx, desty)
    
    # 만약 승객을 목적지까지 못 태웠으면 flag = False
    if new_temp == False:
        flag = False
        break
        
    # 현재 목적지를 새로운 출발지로 저장
    sx, sy, go_dist = new_temp.pop()
    
    # 목적지까지 가는데 걸린 거리를 현재 연료에서 뺌
    k -= go_dist
    
    # 만약 현재 남아있는 연료보다 거리가 더 길면 목적지까지 못간 것이므로 flag = False
    if k < 0:
        flag = False
        break
        
    # 목적지까지 갔으면 가는데 걸린 거리 * 2 만큼 연료를 더함
    else:
        k += go_dist*2

if flag == True:
    print(k)
else:
    print(-1)