[SWEA] 1795_인수의 생일 파티 (다익스트라 이용)

📕 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4xuqCqBeUDFAUx 

SW Expert Academy

 

💡 풀이법

1. dijkstra1은 각 집에서 인수의 집으로 가는 최단 거리를 구하는 함수이다.

2. 인수의 집을 출발지로 생각하고 반대로 거슬러 올라간다.

3. 그렇기 때문에 인접한지 인접하지 않은지 확인할때 다음 노드에서 현재 노드로 연결되어있는지를 확인해야 한다.

4. dp는 인수의 집(도착지)에서 각 노드들까지 가는 최단 거리가 담기게 된다.

5. dijkstra2은 인수의 집에서 각자의 집으로 가는 최단 거리를 구하는 함수이다.

6. 이때는 인수의집이 출발지이고 각 노드들로 가는 최단거리가 dp에 담기게 된다.

7. 두개의 다익스트라 함수가 실행이 되고 나면  dp1, dp2에는 각자의 집에서 인수의 집으로 가는 최단거리와, 인수의집에서 각자의 집으로 가는 최단거리가 담기게 된다.

8. for문을 돌며 zip을 이용해 두개의 리스트에서 거리를 가지고와서 둘을 합한 값이 ans보다 크면 ans를 바꾼다.

 

from collections import deque

def dijkstra1(start):
    dp = [float('inf') for _ in range(N+1)]
    deq = deque([start])
    dp[start] = 0

    while deq:
        n = deq.popleft()
        for v in range(1, N+1):
            if matrix[v][n]:
                if dp[v] > dp[n] + matrix[v][n]:
                    dp[v] = dp[n] + matrix[v][n]
                    deq.append(v)
    return dp

def dijkstra2(start):
    dp = [float('inf') for _ in range(N+1)]
    deq = deque([start])
    dp[start] = 0

    while deq:
        n = deq.popleft()
        for v in range(1, N+1):
            if matrix[n][v]:
                if dp[v] > dp[n] + matrix[n][v]:
                    dp[v] = dp[n] + matrix[n][v]
                    deq.append(v)
    return dp

T = int(input())
for tc in range(1, T+1):
    N, M, X = map(int, input().split())
    matrix = [[0 for _ in range(N+1)] for _ in range(N+1)]

    for _ in range(M):
        x, y, c = map(int, input().split())
        matrix[x][y] = c

    dp1 = dijkstra1(X)
    dp2 = dijkstra2(X)

    ans = 0
    for i, j in zip(dp1[1:], dp2[1:]):
        ans = max(ans, i+j)
    print('#{} {}'.format(tc, ans))