문제

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

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

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

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

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

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

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

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

<그림 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을 출력한다.

아이디어

✅ 손님을 모두 태울때까지 반복한다.

• 택시(출발지)로부터 벽이 아닌 곳으로 갈 수 있는 칸의 모든 거리를 계산한다. => (distance 함수로 만들기)

• 손님의 위치를 찾아서 가장 가까운 거리의 손님부터 태운다.

• 손님을 태우면 택시가 손님 위치로 가야하므로 택시의 위치를 해당 손님의 위치로 바꾼다.

• 손님 위치까지 가는데에 사용된 연료는 택시의 처음 위치와 손님의 거리이므로 '기존 연료 - 사용된 연료(손님과 택시의 거리)'를 하고 0 이하이면 갈 수 없거나 목적지로 갈 수 없기 때문에 -1을 return한다.

• 다시 distance함수를 이용해서 바뀐 택시 위치(손님의 출발 위치)로 부터의 모든 거리를 계산하고 목적지까지의 거리를 구한다.

• 목적지까지의 거리가 사용해야하는 연료이므로 '기존 연료 - 목적지까지 거리'를 했을 때 0보다 작으면(0이면 목적지 도착가능) 갈 수 없으므로 -1을 return 한다.

• 갈 수 있으면 '연료 + (거리 * 2)'를 하고 택시의 위치를 목적지 위치로 변경한다.

• 해당 손님은 이동을 완료했기 때문에 people리스트에서 삭제한다.

✅ distance함수

• 출발 위치를 1로 설정하기 때문에 마지막에 하나를 빼줘야 한다.
  (거리가 0인 경우는 갈 수 없는 곳이기 때문에 1을 빼면 -1이 나온다.)
• 처음 arr를 deepcopy를 이용해 복사한다. (copy를 이용하면 안된다 참고링크)
• deque를 이용한다.
• queue에서 하나를 제거한 후 상하좌우 방향을 조사해서 범위가 맞고, 0이면(아직 방문 안함) queue에 추가한 후, 하나를 더해 저장한다.
• 마지막에 배열 전체를 return해서 원하는 위치까지의 거리를 구할 수 있도록 한다.

[#Error] 내 코드_python

:: 조건 추가 안 함(승객의 거리가 같으면 행, 열 순서로 작은 승객 먼저 태우기)

from collections import deque
import copy

n, m, oil = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]
taxi = list(map(int, input().split()))
taxi[0] -= 1
taxi[1] -= 1
people = [list(map(int, input().split())) for x in range(m)]
direction = [[-1, 0], [1, 0], [0, 1], [0, -1]]


def distance(start, finish):
    a = copy.deepcopy(arr)
    a[start[0]][start[1]] = 1
    queue = deque()
    queue.append(start)
    while queue:
        s = queue.popleft()
        x = s[0]
        y = s[1]
        if x == finish[0] and y == finish[1]:
            return a[x][y]-1
        for i in range(4):
            nx = x + direction[i][0]
            ny = y + direction[i][1]
            if 0 <= nx < n and 0 <= ny < n:
                if a[nx][ny] == 0:
                    queue.append([nx, ny])
                    a[nx][ny] = a[x][y] + 1
    return 0


while len(people) > 0:
    d = []
    for i in range(len(people)):
        di = distance(taxi, [people[i][0]-1, people[i][1]-1])
        d.append([i, di])
    d.sort(key= lambda x: (x[1]))
    if d[0][1] == 0:    #거리가 0이 나올 수 없음
        oil = -1
        break
    idx = d[0][0]
    oil -= d[0][1]
    if oil <= 0:    #승객한테 갈 수 없음
        oil = -1
        break
    taxi = [people[idx][0] - 1, people[idx][1] - 1]
    oil -= distance(taxi, [people[idx][2]-1, people[idx][3]-1])
    if oil < 0: #목적지 도착 못함
        oil = -1
        break
    oil += distance(taxi, [people[idx][2]-1, people[idx][3]-1]) * 2
    taxi = [people[idx][2]-1, people[idx][3]-1]
    del people[idx]
print(oil)

[#Error] 내 코드_python

:: 위에서 빠진 조건 추가했지만 시간초과

from collections import deque
import copy

n, m, oil = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]
taxi = list(map(int, input().split()))
taxi[0] -= 1
taxi[1] -= 1
people = [list(map(int, input().split())) for x in range(m)]
direction = [[-1, 0], [1, 0], [0, 1], [0, -1]]


def distance(start, finish):
    a = copy.deepcopy(arr)
    a[start[0]][start[1]] = 1
    queue = deque()
    queue.append(start)
    while queue:
        s = queue.popleft()
        x = s[0]
        y = s[1]
        if x == finish[0] and y == finish[1]:
            return a[x][y]-1
        for i in range(4):
            nx = x + direction[i][0]
            ny = y + direction[i][1]
            if 0 <= nx < n and 0 <= ny < n:
                if a[nx][ny] == 0:
                    queue.append([nx, ny])
                    a[nx][ny] = a[x][y] + 1
    return -1


while len(people) > 0:
    d = []
    for i in range(len(people)):
        di = distance(taxi, [people[i][0]-1, people[i][1]-1])
        d.append([people[i][0]-1, people[i][1]-1, di, i])
    d.sort(key= lambda x: (x[2], x[0], x[1]))
    if d[0][2] == -1:    #거리가 -1이 나올 수 없음
        oil = -1
        break
    idx = d[0][3]
    oil -= d[0][2]
    if oil < 0:    #승객한테 갈 수 없음
        oil = -1
        break
    taxi = [people[idx][0] - 1, people[idx][1] - 1]
    dist = distance(taxi, [people[idx][2]-1, people[idx][3]-1])
    oil -= dist
    if oil < 0: #목적지 도착 못함
        oil = -1
        break
    oil += dist * 2
    taxi = [people[idx][2]-1, people[idx][3]-1]
    del people[idx]
print(oil)

내 코드_python

:: 택시에서 승객 위치를 구할 때 한 명씩 하는 것이 아니라, 택시부터 거리이기 때문에 출발지가 같으므로 모든 위치의 거리를 구한다.

from collections import deque
import copy

n, m, oil = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]
taxi = list(map(int, input().split()))
taxi[0] -= 1
taxi[1] -= 1
people = [list(map(int, input().split())) for x in range(m)]
direction = [[-1, 0], [1, 0], [0, 1], [0, -1]]  #상하좌우 반복하는 방향

#출발지(start)부터 갈 수 있는 모든 곳의 거리를 구하는 함수
def distance(start):
    a = copy.deepcopy(arr)
    a[start[0]][start[1]] = 1
    queue = deque()
    queue.append(start)
    while queue:
        s = queue.popleft()
        x = s[0]
        y = s[1]
        for i in range(4):
            nx = x + direction[i][0]
            ny = y + direction[i][1]
            if 0 <= nx < n and 0 <= ny < n:
                if a[nx][ny] == 0:
                    queue.append([nx, ny])
                    a[nx][ny] = a[x][y] + 1
    return a


while len(people) > 0:
    d = []  #[승객 위치x, 위치y, 거리, 인덱스] 담을 배역
    d_arr = distance(taxi)  #출발지부터 모든 거리 계산한 배열
    for i in range(len(people)):    #모든 승객의 위치를 계산
        px = people[i][0]-1
        py = people[i][1]-1
        d.append([px, py, d_arr[px][py]-1, i])
    d.sort(key= lambda x: (x[2], x[0], x[1]))   #주어진 조건에 맞춰 거리, 행, 열 순으로 정렬
    if d[0][2] == -1:    #거리가 -1이 나올 수 없음 => 막혀있는 경우
        oil = -1
        break
    idx = d[0][3]   #people의 인덱스
    oil -= d[0][2]  #거리가 필요한 연료이므로 빼줌
    if oil < 0:    #승객한테 갈 수 없음
        oil = -1
        break
    taxi = [people[idx][0] - 1, people[idx][1] - 1] #택시가 손님의 위치로 이동함
    d_arr = distance(taxi)
    dist = d_arr[people[idx][2]-1][people[idx][3]-1]-1  #목적지까지의 거리
    oil -= dist
    if oil < 0: #목적지 도착 못함
        oil = -1
        break
    oil += dist * 2
    taxi = [people[idx][2]-1, people[idx][3]-1] #택시가 손님 목적지로 이동함
    del people[idx] #도착한 손님은 배열에서 제거
print(oil)