거의 최단 경로 (5719번) - 백준 (BOJ)

https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

 

 

백준 - 거의 최단 경로 (Almost Shortest Path) (5719번)

 

난이도 : Platinum 5

알고리즘&자료구조 : Dijkstra (다익스트라)

 

---

 

다익스트라를 응용해서 풀 수 있는 문제이다.

 

일반적인 다익스트라 문제와는 조금 다르게,

가장 빠른 최단거리가 아닌 두 번째로 빠른 최단거리를 구해야 한다.

 

 

< 전체 코드 >

import sys
input = sys.stdin.readline
from heapq import heappop, heappush


class SecondBest():
    def __init__(self, N, M):
        S, D = map(int, input().split())
        graph = [[] for _ in range(N)]
        for _ in range(M):
            U, V, P = map(int, input().split())
            graph[U].append((P, V))
        memo = [[] for _ in range(N)]

        dist = [sys.maxsize] * N
        dist[S] = 0
        pq = [(0, S)]
        while pq:
            pd, pn = heappop(pq)
            if dist[pn] < pd:
                continue
            for cd, cn in graph[pn]:
                if pd+cd < dist[cn]:
                    dist[cn] = pd+cd
                    heappush(pq, (pd+cd, cn))
                    memo[cn] = [pn]
                elif pd+cd == dist[cn]:
                    memo[cn].append(pn)

        exclude = [set() for _ in range(N)]
        stack = [(D, memo[D])]
        while stack:
            cn, pns = stack.pop()
            for pn in pns:
                if cn in exclude[pn]:
                    continue
                exclude[pn].add(cn)
                stack.append((pn, memo[pn]))

        dist = [sys.maxsize] * N
        dist[S] = 0
        pq = [(0, S)]
        while pq:
            pd, pn = heappop(pq)
            if dist[pn] < pd:
                continue
            for cd, cn in graph[pn]:
                if cn in exclude[pn]:
                    continue
                if pd+cd < dist[cn]:
                    dist[cn] = pd+cd
                    heappush(pq, (pd+cd, cn))

        self.answer = -1 if dist[D] == sys.maxsize else dist[D]
        

if __name__ == '__main__':
    while True:
        N, M = map(int, input().split())
        if N == M == 0:
            break
        tc = SecondBest(N, M)
        print(tc.answer)

 

 

 

---

① 일반적인 다익스트라를 진행한다.

dist = [sys.maxsize] * N
dist[S] = 0
pq = [(0, S)]
while pq:
    pd, pn = heappop(pq)
    if dist[pn] < pd:
        continue
    for cd, cn in graph[pn]:
        if pd+cd < dist[cn]:
            dist[cn] = pd+cd
            heappush(pq, (pd+cd, cn))
            memo[cn] = [pn]
        elif pd+cd == dist[cn]:
            memo[cn].append(pn)

 

다만, 각 노드에 최단경로로 접근하는 자식 노드들을 memo에 기록해줘야 한다.

 

 

 

② 위에서 찾아낸 memo의 최단경로들을, exclude에 담아둔다.

(DFS 알고리즘과 set 자료구조를 활용했다.)

exclude = [set() for _ in range(N)]
stack = [(D, memo[D])]
while stack:
    cn, pns = stack.pop()
    for pn in pns:
        if cn in exclude[pn]:
            continue
        exclude[pn].add(cn)
        stack.append((pn, memo[pn]))

 

 

 

③ 다시 한 번 다익스트라를 진행하는데,

위에서 exclude에 담아둔 최단경로들은 제외한다.

dist = [sys.maxsize] * N
dist[S] = 0
pq = [(0, S)]
while pq:
    pd, pn = heappop(pq)
    if dist[pn] < pd:
        continue
    for cd, cn in graph[pn]:
        if cn in exclude[pn]:
            continue
        if pd+cd < dist[cn]:
            dist[cn] = pd+cd
            heappush(pq, (pd+cd, cn))

 

 

 

④ 위에서 다익스트라를 진행한 후,

D 까지의 거리를 확인하고 출력한다.

self.answer = -1 if dist[D] == sys.maxsize else dist[D]