백준 / 1504 / 특정한 최단 경로 / C++

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

1504번: 특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

풀이

특별한 조건을 만족하는 경로중에서 최단경로를 구하는 문제였습니다. 좀 어렵고 복잡해 보일 수록 분할 정복 알고리즘 처럼 문제를 작은 또 하나의 문제로 쪼개서 그 부분을 먼저 해결하고 그걸 이용하여 결국에는 큰 문제를 해결하는 방향으로 생각하는게 큰 도움이 되는 것 같습니다.

 

1번에서 N번까지 주어진 두개의 정점을 모두 지나가면서 갈려고 하면 어떻게 가는 방법이 있을까요 ? 반드시 지나야 하는 두개의 정점을 a,b라고 하겠습니다.

1) 1번에서 a까지 최단거리로 이동, a에서 b까지 최단거리로 이동, b에서 N까지 최단거리로 이동.

이렇게 하면 a,b를 지나가면서 1에서 N까지 최단거리로 이동할 수 있습니다. 하지만 한가지의 경우가 더있죠.

2) 1번에서 b까지 최단거리로 이동, b에서 a까지 최단거리로 이동, a에서 N까지 최단거리로 이동.

이 외에는 1에서 N까지 최단거리로 a,b를 경유해서 가는 방법은 없습니다.

 

그래프에서 최단경로를 구하는데 보통 많이 사용되는 dijkstra로 코드를 구현했습니다. 시작점과 도착점을 인자로 넘겨서 시작점에서 모든 노드까지의 최단거리를 구했을 때, 도착지 까지의 최단거리 값을 return해서 더하는 방식으로 1번과 2번의 값을 구하고 만약 그러한 경로로 이동할 수 없다면 maxDistance값을 포함할 것을 이용하여 출력 처리를 통해 문제를 해결해봤습니다. 코드에서 궁금하신 부분 있으시면 댓글남겨주세요. 최선을 다해서 설명해드리겠습니다!