https://www.acmicpc.net/problem/22870
문제 요약
가중치 있는 크기 N(N <= 200,000)의 무향 그래프에 대해,
정점 s에서 e로 가는 최단 거리와 다시 e에서 s로 돌아오는 최단 거리의 합을 계산한다.
단 e에서 s로 돌아오는 경로에서는 s에서 e로 가는 최단 경로 중간에 방문한 정점을 방문해서는 안 된다.
→ s와 e는 당연히 방문 가능
s에서 e로 가는 최단경로는 여러 개 존재할 수 있으므로, 사전 순으로 먼저 오는 경로를 선택한다.
→ 경로에 포함된 정점 번호를 앞에서부터 하나씩 비교하면 된다. 1-3-5보다 1-2-3-4가 사전 순으로 먼저 온다.
핵심 아이디어
다익스트라
- 경로 뒤집기
- 최적 해 찾기
- 특정 정점 제외하고 계산
0.
음의 가중치가 없고 크기가 큰 그래프의 최단 경로를 계산해야 하므로 다익스트라를 사용하자.
s에서 e로 가는 건 단순 다익스트라로 충분한데, e에서 s로 돌아올 때는 특정 정점을 제외한 최단 거리를 계산해야 한다.
특정 정점을 결정하려면, s에서 e로 최단 거리로 이동할 때 지나야 하는 정점, 즉 최적 해도 찾아야 한다.
1.
먼저 최적 해를 구하는 방법부터 알아보자. 원리만 두고 보면 간단하다. 학생 때 배운 수학적 귀납법이 떠오르기도 한다.
최단 경로에 포함되는 정점 a와 a에 인접한 정점 b에 대해, dist[a] - ab = dist[b]이면 b도 최단 경로에 포함된다.
( dist[a], dist[b] : 다익스트라로 계산한 시작 정점과의 최단 거리, ab : a, b를 연결하는 간선의 가중치 )
최적 해를 빠르게 계산하는 데 도움이 되는 유용한 원리이므로 알아두면 좋다.
이를 가지고 s에서 e로 가는 최적 해를 찾는 코드는 이런 식이다.
vector<int> dist;
//e에서 s로 돌아가며 최적 해를 찾는다
void backtrack(int cur){
//cur를 최적 해에 추가
//...
//s에 도착
if(cur == s)
return;
//Edge => v : 정점 번호, w : 두 정점 사이 거리
//인접한 정점에 대해
for(Edge nxt : graph[cur])
if(dist[nxt.v] == dist[cur] - nxt.w)
backtrack(nxt.v);
}
int main() {
dist = dijkstra(s, e);
//e는 반드시 최적 해에 포함된다
backtrack(e);
}
e에서 출발한다는 것만 기억하면 어렵지 않게 구현할 수 있다.
2.
그러나 위 코드는 어떤 정점에 대해,
그 정점이 여러 개의 가능한 최단 경로 중 하나에만 포함되어도 최적 해에 포함해버린다.
문제에서 요구하는 최적 해는 사전 순으로 가장 앞서야 하므로, 우리는 최적 해를 찾을 때 그 중 하나만 선택해야 한다.
인접한 정점들에 대해, 최적 해에 포함될 수 있는 정점 중 그 번호가 가장 작은 정점만 선택하면 되지 않을까?
아쉽게도 불가능하다. 우리는 역주행을 하고 있기 때문이다.
다음 그래프를 보자.
간선의 가중치가 모두 1이라고 하면, 1에서 6으로 가는 최단 경로는 1-2-5-6과 1-3-4-6 2가지가 있다.
최적 해를 찾기 위해서는 6에서 1로 역주행을 하게 되는데, 번호가 작은 정점을 선택하면
결과적으로 1-3-4-6 경로가 선택돼버린다.
문자열을 비교할 때와 비슷하다. 문자를 뒤에서부터 비교하면 "acdf"와 "abef" 중 acdf가 앞선다는 잘못된 결과가 나온다.
3.
그럼 어떡하지? 사실 이 부분이 문제의 핵심이라고 생각한다. 간단한 발상의 전환으로 해결할 수 있다.
"비교할 문자열(경로)를 뒤집으면 어떨까?"
다시 말해 문자열(경로)을 뒤에서부터 비교할 수밖에 없다면, 문자열(경로)을 한번 뒤집은 채로 비교하면 된다.
위의 두 문자열을 뒤집은 "fdca"와 "feba"를 뒤에서부터 비교하면
"feba", 즉 원래는 abef인 문자열이 앞선다는 올바른 결과가 나온다.
원래 dijkstra(s, e); backtrack(e);로 계산하던 경로를 dijkstra(e, s); backtrack(s);로 방향만 바꿔주면
간단하게 경로를 뒤집을 수 있다.
이제 기존에 하려던 대로, 인접하고 최적 해에 포함되는 정점 중 번호가 가장 작은 정점만 선택해 표시해주면 된다.
4.
다익스트라 알고리즘에서 특정 정점을 고려하지 않게 하려면 간단한 코드 한줄만으로 충분하다.
최적 해 정점들을 크기 N의 불리언 배열에 표시해두고,
다익스트라를 계산할 때 이번에 선택한 정점과 인접한 정점들에 대해 표시가 돼있는지만 확인하면 된다.
for(auto p : graph[u]){
int v = p.first, uv = p.second;
//조건문 추가
if(used[v]) continue;
if(dist[v] > uv + w)
pq.push({dist[v] = uv + w, v});
}
코드 (구현부 생략)
void solve() {
//그래프 입력받기
input();
cin >> s >> e;
//방향 반전
vector<int> dist = dijkstra(e, s);
//s에서 e로 가는 최단 거리 = e에서 s로 가는 최단 거리 (무향 그래프이므로)
int se = dist[s];
//뒤집은 경로를 역주행
backtrack(s, e, dist);
//정점 s와 e는 제외하면 안 됨
dist[s] = dist[e] = false;
//e에서 일부 정점을 제외하고 s로 가는 최단 거리
dist = dijkstra(e, s);
int es = dist[s];
cout << se + es << endl;
}