[BOJ/Python] 9694_무엇을 아느냐가 아니라 누구를 아느냐가 문제다

문제 출처:https://www.acmicpc.net/problem/9694

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

문제

한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한것이라고 믿고있다. 다음달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다.

이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날수 없다면 그를 알고있는 인맥을 이용하여 만날것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다.

최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4]

[두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(enemy)는 존재하지 않는다.]

한신이는 지인보다는 최측근 친구에게 소개받기 원한다. 그래서 최고의원을 만나기까지의 인맥간 친밀도의 합을 최소화하고 싶어한다.

N명의 정치인 명단으로부터 그들의 인맥 친밀도가 주어진다. 정치인 리스트를 보고 한신이가 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하면 된다.

 

입력

맨위 첫 번째 줄에 T(1 <T< 100)는 테스트케이스 수를 의미한다. 이것을 따라 다음줄에 각 테스트 케이스가 주어지는데, 첫 번째 줄에는 N과 M이 주어진다. N(N ≤ 20)은 관계의 개수를 의미하며, M(5 ≤M≤ 20)은 정치인의 수를 나타낸다. 이 다음 N줄에는 정치인 x, 그의 친구 y (0 ≤x,y< M), 두사람간의 친밀도 z(1 ≤z≤ 4)를 입력받는다. 정치인 0번은 한신이를 나타내고 M-1은 최고의원을 의미한다.

출력

각 테스트 케이스는 "Case #x: "의 형식으로 출력되며 x는 케이스 번호(1부터 시작)을 의미한다. 콜론뒤에 한신이가 최고의원을 만날수 있다면 0번 정치인(한신이)를 시작으로 M-1번 정치인(최고의원)까지 만난 순서대로 출력하면 되고, 최고의원을 만날수 없는 경우엔 -1을 출력하면 된다.

예제 입력 1

2
7 5
0 1 2
1 3 4
0 2 1
0 4 3
3 2 3
3 4 4
2 4 1
3 5
0 1 2
1 3 4
4 2 1

예제 출력 1

Case #1: 0 2 4
Case #2: -1

힌트

첫 번째 테스트 케이스에서 보면 한신이는 1번 정치인(한신이의 측근[2])에게 3번 정치인(1번 정치인의 지인[4])을 소개받고, 이 3번 정치인은 4번 정치인(3번 정치인의 지인[4])을 만나는 경우 2+4+4 = 10이다.

한신이가 곧바로 4번 정치인(한신이의 비즈니스관계[3])에게 얘기할수 있지만 대신에 2번 정치인(한신이의 최측근[1])에게 4번 정치인(2번 정치인의 최측근[1])을 소개 받아 만난다면 한신이는 더 좋은 인상으로 최고의원을 만날수 있을것이다.

---

풀이

 

1. M명의 정치인이 존재한다.
2. 한신이는 0번 정치진이고, 최고의원은 M-1번 정치인이다.
3. 각 정치인들 사이에는 친밀도가 존재할 수 있는데, 이는 1~4까지 존재하며 낮을수록 더 친밀하다.
4. 한신이가 최고의원까지 친밀도의 합을 최소로 하여 만날 수 있는지 출력하는 문제이다.
5. 만날 수 있다면, 정치인들을 만난 순서를 출력하고 아니라면 -1을 출력한다.

 

풀이는 다음과 같다.

1. 여기서 M명의 정치인은 노드이고, 정치인들 사이의 친밀도는 간선의 가중치라고 할 수 있다.
2. 따라서, 0번부터 M-1번까지 가중치의 합을 최소로 할 수 있는 경로를 찾는 문제가 된다.
3. 그러므로 다익스트라 알고리즘을 이용하여 최단경로를 구한다.

코드는 다음과 같다.

 

import sys
import heapq
 
INF = int(1e9)
 
def dijkstra():
    queue = []
    distance[0] = 0
    heapq.heappush(queue,(0,0))
 
    while queue:
        dist,node = heapq.heappop(queue)
        if node==m-1:
            return True
 
        if dist> distance[node]:
            continue
        
        for next in graph[node]:
            cost = next[1] + dist
            if distance[next[0]] > cost:
                distance[next[0]] = cost
                pre[next[0]] = node
                heapq.heappush(queue,(cost,next[0]))
    return False
 
 
t = int(sys.stdin.readline())
for case in range(1,t+1):
    n,m = map(int,sys.stdin.readline().split())
    distance = [INF for _ in range(m)]
    pre = [i for i in range(m)]
    graph = [[] for _ in range(m)]
    for _ in range(n):
        x,y,z = map(int,sys.stdin.readline().split())
        graph[x].append((y,z))
        graph[y].append((x,z))
 
    print("Case #",case,": ",sep='',end='')
    if dijkstra():
        result = [m-1]
        p = pre[m-1]
        while p !=0:
            result.append(p)
            p = pre[p]
        result.append(p)
 
        print(*result[::-1])
    else:
        print(-1)

• heapq 모듈을 import 하여 우선순위 큐를 이용한다.
• distance 리스트는 0번 노드부터 각 노드까지의 최단거리 리스트이다.
• pre 리스트는 최단거리의 경로를 출력하기 위하여, 해당 노드가 이전에 어떤 노드에서 도달하였는지의 정보를 담은 리스트이다. 예를 들어 2번 노드 -> 4번 노드의 경로라면, pre [4] = 2가 된다.
• 최종적으로 0번 노드에서 m-1번 노드까지의 최단경로를 구해야 하므로, m-1번 노드에 도달한다면 True를 return 하여 함수에서 빠져나오고, 도달하지 못한다면 False를 return 한다.
• True라면 경로를 출력하고, False라면 -1을 출력한다.