17940 - 지하철
📌 문제
대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매우 싫어한다. 그래서 A와 B는 모두 상대 회사의 지하철로 환승할 때 마다 비싼 요금을 받고 있다.
형욱이는 가난한 대학원생이기 때문에 돈을 아끼는 것이 가장 중요하다. 형욱이에게 최적의 출근경로를 찾아주자. 최적의 출근 경로란 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로이다. 여기에서의 환승은 이동하면서 지하철역을 운영하는 회사가 바뀔 때 마다 환승 1회로 계산한다.
위의 그림에서 원은 지하철역을 의미하고 선들은 지하철역들이 연결되어 있는 지를 나타낸다. 흰색으로 표시된 지하철역은 A회사가 운영하는 지하철역이고 검은색으로 표시된 역은 B회사가 운영하는 지하철역이다. 이 때 붉게 표시된 경로로 이동하는 것이 환승 2회로 가장 적게 환승하면서 시간이 가장 짧은 경로이다.
📋 코드
import heapq
INF = int(1e9)
BASE = 10**6
def dijkstra(start, distance):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if dist <= distance[now]:
for pos, c in graph[now]:
cost = dist + c
if cost < distance[pos]:
distance[pos] = cost
heapq.heappush(q, (cost, pos))
N, M = map(int, input().split())
company = [int(input()) for _ in range(N)]
tmp = [list(map(int, input().split())) for _ in range(N)]
graph = [[] * N for _ in range(N)]
result = [[] * N for _ in range(N)]
for i in range(N):
for j in range(N):
if tmp[i][j] != 0:
if company[i] == company[j]:
graph[i].append((j, tmp[i][j]))
else:
graph[i].append((j, tmp[i][j] + BASE))
distance = [INF for _ in range(N)]
dijkstra(0, distance)
count, time = distance[M] // BASE, distance[M] % BASE
print(count, time)💡 한마디
소요시간보다 중요한 것은 환승 횟수이다. 문제에서 준 조건에 의하면 2번 환승하고 5분 걸리는 것보다 1번 환승하고 10000분 걸리는 것이 더 낫다. 그래서 환승하는 경우 (i 와 j 가 다른 경우) 상수 BASE 만큼을 더해주고, 다익스트라 알고리즘을 돌렸다.
