9694 - 무엇을 아느냐가 아니라 누구를 아느냐가 문제다
📌 문제
한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한것이라고 믿고있다. 다음달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다.
이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날수 없다면 그를 알고있는 인맥을 이용하여 만날것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다.
최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4]
[두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(enemy)는 존재하지 않는다.]
한신이는 지인보다는 최측근 친구에게 소개받기 원한다. 그래서 최고의원을 만나기까지의 인맥간 친밀도의 합을 최소화하고 싶어한다.
N명의 정치인 명단으로부터 그들의 인맥 친밀도가 주어진다. 정치인 리스트를 보고 한신이가 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하면 된다.
📋 코드
import heapq
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] >= dist:
for pos, c in graph[now]:
cost = dist + c
if cost < distance[pos]:
tmp[pos] = now
q.append((cost, pos))
distance[pos] = cost
X = int(input())
for x in range(1, X+1):
N, M = map(int, input().split())
graph = [[] for _ in range(M)]
distance = [int(1e9) for _ in range(M)]
tmp = [-1 for _ in range(M)]
for _ in range(N):
a, b, cost = map(int, input().split())
graph[a].append((b, cost))
graph[b].append((a, cost))
dijkstra(0)
result = [M-1]
idx = M-1
while tmp[idx] != -1:
idx = tmp[idx]
result.append(idx)
result.reverse()
if len(result) == 1:
result = [-1]
print('Case #{}:'.format(x), *result)💡 한마디
단순한 최단 경로 문제인 줄 알았는데, 생각보다 직접적인 경로를 찾는 데 애먹었다.
