1504번: 특정한 최단 경로 (acmicpc.net)
위 문제의 경우
1번 정점 --> N번 정점까지의 최단 거리를 구하되,
입력으로 주어지는 v1, v2번 정점을 반드시 지날 때의 최단 경로를 구해야 하는 문제입니다.
그래서 오랜 시간 고민하고 반례들을 살펴보면서 저는 다음과 같이 풀었습니다.
( 코드 주소: http://boj.kr/14bc4f5fbec144afaa3073ab21aceebd ) (링크 수정했습니다. 죄송합니다 ㅠㅠ)
------------------------------------------------------------------
<아이디어>
1번 정점 --> N번 정점까지의 최단 경로를 p (path의 p)라 하자.
그럼 v1과 p 사이의 최단 거리를 생각할 수 있다. --> 이 최단 거리를 ( p 상의 모든 점들과 v1의 최단 거리 )의 최솟값으로 정의하고,
( p 상의 모든 점들과 v1의 최단 거리 )가 최소가 되도록 하는 p 상의 점을 편의상 수선의 발 p1이라 부르자.
마찬가지로 v2에 대해서도 위의 최단 거리 및 수선의 발(p2) 을 생각할 수 있고, 이때 문제의 답은 아래의 두 값중 최솟값이다.
dist(1, p1) + dist(p1, v1) + dist(v1, v2) + dist(v2, N)
dist(1, p2) + dist(p2, v2) + dist(v2, v1) + dist(v1, N) // 이때 주어진 그래프는 무방향 그래프여서 dist(v1, v2) = dist(v2, v1).
(만약 두 값 모두 무한대 값이라면 문제에서 요구한대로 -1 출력)
------------------------------------------------------------------
다행히 문제에서 기본적으로 요구한 1초 제한을 파이썬으로도 맞출 수 있었고 (920 ~ 930ms) 그래서 한 건 해냈다라는 느낌으로 넘어가려고 했는데...
질문 게시판과 맞힌 사람들을 살피다보니 뭔가 더 간단한 방법이 있다는 느낌이 들었습니다.
특히 위 아이디어를 구현하다보니 dijkstra만 5번을 해야해서 구현하면서도 뭔가 찝찝했고요.
혹시 더 간단하거나 시간 복잡도를 더 줄이는 (상수 커팅이라도 좋습니다) 방법이 있는 것일까요?
늘 긴 질문글 들고 와서 죄송합니다 ㅠㅠ
링크 수정했습니다. 죄송합니다 ㅠㅠ
v1과 v2를 반드시 지나면서 최단거리를 가지려면 1에서 v1, v1에서 v2, v2에서 N을 거쳐 가는 것과 1에서 v2, v2에서 v1, v1에서 N을 거쳐 가는 것의 두 가지가 있습니다.
즉 dist(1, v1) + dist(v1, v2) + dist(v2, N) 과 dist(1, v2) + dist(v2, v1) + dist(v1, N) 을 구해서 비교하면 되는데요, 이때 간선이 전부 양방향이므로 dist(1, v1) = dist(v1, 1) 임을 이용해 다익스트라를 v1, v2를 시작점으로 총 2번 돌려 거리들의 값을 구해줄 수 있습니다.
수선의 발은 아이디어는 나쁘지 않지만 찾지 않아도 됩니다. 정점 1에서 v1으로 가는 최단 경로를 찾는다 할때 수선의 발인 정점 p1이 있다고 생각해보면,
1에서 v1으로 가는 최단경로가 p1을 지남: 이 경우는 dist(1, v1) = dist(1, p1) + dist(p1, v1) 일 것입니다. 즉 p1을 찾지 않아도 값을 다익스트라 시행으로 얻을 수 있습니다. 1에서 v1으로 가는 최단경로가 p1을 안 지남: p1을 지나지 않으므로 p1을 찾지 않아도 됩니다. 따라서 수선의 발을 찾는 과정은 생략해도 됩니다.
처음에 저도 말씀해주신 대로 풀까하다가 어떻게 증명할지 몰라 수선의 발을 생각했었는데 이렇게 가정해보는 방법이 있군요. 감사합니다. 또 한 수 배우고 갑니다.