[백준] 1504 특정한 최단경로
·
Algorithm/Algorithm (문제풀이)
🔒 문제 🧠 아이디어 반드시 2개의 정점을 경유해서 가야하므로 Way point (경유지) 1, 2 가 존재할 때 선택할 수 있는 경로는 다음 2가지로 좁혀진다. 출발 노드 -> 경유지 1 -> 경유지 2 -> 목적지 출발 노드 -> 경유지 2 -> 경유지 1 -> 목적지 여기서 구해야 할 값은 다음 5가지다. 출발 노드 -> 경유지 1의 최단경로 출발 노드 -> 경유지 2의 최단경로 경유지 1 -> 목적지의 최단경로 경유지 2 -> 목적지의 최단경로 경유지 1 - 경유지2 의 최단경로 양방향 그래프기 때문에 경유지 1-> 경유지 2, 경유지 2-> 경유지1는 서로 거리가 같기 때문에 한 번만 구하면 된다. 최단 경로를 구해야하므로 Dijkstra 알고리즘 사용한다. 출발 노드 -> 경유지 1,2 는 한..