[BOJ] 13424번 비밀 모임 / 사용언어 : 파이썬(python)

※ 문제링크 

13424번: 비밀 모임

해당 문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 파이썬에서는 heapq로 최소힙을 지원해주고 있기에 해당 라이브러리를 사용해서 문제를 해결하였다. 다익스트라 알고리즘으로 각 방에서 다른 방으로의 최소 거리를 구한 후에 해당 값들을 하나의 리스트에 저장해주고, 종료 후에 가장 작은 거리값을 가지는 방의 이름을 출력해주면 되는 문제로, 다익스트라 알고리즘을 구현할 수 있다면 크게 어렵지 않은 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다.

1. 입력받은 값들 바탕으로 테스트케이스를 돌릴 수 있게 반복문을 구성하고, 각각의 변수와 리스트를 활용하여 조건변수들과 그래프 자료구조를 구현해준다.(그래프는 문제조건상 양방향으로 판단하였다.)

2. 각각의 방에서 다른 방으로 가는 최단거리를 구할 수 있는 다익스트라 알고리즘을 구현한다.

3. 사전에 저장해둔 친구들의 위치만큼 반복문을 돌려서 각각의 방에 대한 최단거리 합을 구해주고, index함수를 이용해서 가장 작은 거리값을 가지는 가장작은 방의 번호를 출력해준다.(시간 및 메모리 절감을 위해 sys를 사용해주었다.)

 

from heapq import heappush, heappop
import sys

def dijkstra(numbers):
    heap = []
    dp = [float('inf') for _ in range(N+1)]
    dp[numbers] = 0
    heappush(heap, [0, numbers])

    while heap:
        dt1, r_n1 = heappop(heap)
        for dt_s in graph[r_n1]: 
            dt2, r_n2 = dt_s
            if dt1 > dp[r_n1]:
                continue
            dt3 = dt1 + dt2
            if dt3 < dp[r_n2]:
                dp[r_n2] = dt3
                heappush(heap, [dt3, r_n2])

    for i in range(len(dp)):
        if ans[i] == float('inf'):
            ans[i] = 0
            ans[i] += dp[i]
        else:
            ans[i] += dp[i]

# input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N, M = map(int, input().split()) # N: 방의 개수 / M: 통로의 개수
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        r1, r2, dt = map(int, input().split())
        graph[r1].append([dt, r2])
        graph[r2].append([dt, r1])
    K = int(input()) # K: 친구의 수

    loc_f = list(map(int, input().split()))
    ans = [float('inf') for _ in range(N+1)]
    for number in loc_f:
        dijkstra(number)
    print(ans.index(min(ans)))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.