🥇 19238 스타트 택시
문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.
입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
분석
문제 지문이 길지만, 지문에서 요구하는 것들을 구현해 주면 된다. 하지만 정답 비율이 19%인 이유가 있다..ㅠㅠ 한 승객의 출발지가 다른 승객의 도착지가 될 수 있으며, 모든 승객의 도착지는 같을 수 있다는 점을 주의해야 한다.
택시에서 가장 가까운 승객을 찾을 때에는 다익스트라 알고리즘을 사용해서 현재 택시와의 거리를 구한다. 힙을 이용해서 최단 거리를 구해주고 bfs()로 승객의 도착지 최단거리를 찾아준다.
소스코드
import sys
from collections import deque, defaultdict
from heapq import heappop, heappush
input = sys.stdin.readline
N, M, fuel = map(int, input().split())
board_start = [list(map(int, input().split())) for _ in range(N)] # 0 빈공간 1 벽
taxi = list(map(int, input().split()))
taxi[0] -= 1
taxi[1] -= 1
# 각 고객마다 도착지가 겹칠 수 있기 때문에 딕셔너리로 저장함
board_end = defaultdict(list)
for i in range(2, M + 2):
# 출발지 행,열 / 도착지 행, 열
sx, sy, ex, ey = map(int, input().split())
# 0, 1 은 이미 사용 중이므로 2부터 (2,B) ~
board_start[sx - 1][sy - 1] = i
board_end[i] = [ex-1, ey-1]
# 택시 주위에 가장 가까운 고객을 찾는 메서드
def shortest_distances(x, y):
distances = [[int(1e9) for _ in range(N)] for _ in range(N)]
distances[x][y] = 0
q = [(0, x, y)]
while q:
d, x, y = heappop(q)
if d > distances[x][y]:
continue
for nx, ny in (x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1):
if nx < 0 or ny < 0 or nx >= N or ny >= N or board_start[nx][ny] == 1:
continue
cost = d + 1
if distances[nx][ny] > cost:
distances[nx][ny] = cost
heappush(q, (cost, nx, ny))
result = []
for i in range(N):
for j in range(N):
if 2 <= board_start[i][j]: # 빈공간과 벽이 아닌 승객만 저장
heappush(result, [distances[i][j], i, j, board_start[i][j]])
if result:
return heappop(result) # 최단 거리가 가장 짧은 고객, (행의 번호가 작고, 그 다음 열의 번호가 작은 사람)
else:
return -1 # 고객이 더 없을 경우
def arrive(start_x, start_y, client):
global taxi
visited = [[-1 for _ in range(N)] for _ in range(N)]
visited[start_x][start_y] = 0
q = deque([(start_x, start_y)])
while q:
x, y = q.popleft()
if board_end[client][0] == x and board_end[client][1] == y:
taxi = [x, y]
return visited[x][y]
for nx, ny in (x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1):
if nx < 0 or ny < 0 or nx >= N or ny >= N or board_start[nx][ny] == 1 or visited[nx][ny] != -1:
continue
visited[nx][ny] = visited[x][y] + 1 # 거리 계산
q.append((nx, ny))
return -1 # 도착지까지 도달하지 못할 경우
while True:
# 현재 택시와 가까운 고객 찾기
res = shortest_distances(taxi[0], taxi[1])
if res == -1: # 더 이상 탑승할 승객이 없는 경우
break
dist, x, y, client = res # 태울 승객의 정보
board_start[x][y] = 0
if fuel - dist <= 0:
print(-1)
sys.exit(0)
fuel -= dist # 이동한 만큼 연료 제거
# 택시가 승객을 태움
taxi = [x, y]
# 택시가 승객의 도착지까지 이동
arrive_d = arrive(x, y, client)
if arrive_d == -1 or fuel - arrive_d < 0: # 도착지까지 도달할 수 없거나 가는 도중 연료가 떨어졌을 때, 동시에 바닥나는 경우는 예외로 = 제거
print(-1)
sys.exit(0)
fuel += (-arrive_d + (arrive_d * 2)) # 성공적으로 이동시켰으므로 소모한 연료 양 * 2 충전
# 남은 연료 출력
print(fuel)