BOJ 5719 : 거의 최단 경로

문제 링크 : https://www.acmicpc.net/problem/5719

 

이 문제는 BOJ 1948 임계경로와 매우 유사한 문제다.

임계경로는 그래프가 DAG 이고, 최장거리를 구하는 문제여서 위상정렬 DP 로 해결하지만,

이 문제는 그래프가 일반적인 방향그래프이며, 최단거리를 구하는 문제이기에 Dijkstra 가 필요하다.

 

우선 최단거리에 포함되는 간선을 모두 구해야하기에, Dijkstra 역추적이 필요하다.

나는 원래 임계경로 문제를 풀 때 역추적을 비효율적으로 했었다.

N개의 노드마다, 자신을 갱신시킨 노드들의 목록을 vector 로 관리했었는데, 그럴 필요가 없었다.

 

Dijkstra 를 다 돌리고 난 후 dist 값을 비교하면 직전 노드를 직접 저장할 필요가 없다.

예를 들어,  2  -> 5 로 가는 간선의 비용이 10 이라고 하자.

Dijkstra 후에, dist[2] = 12, dist[5] = 22 라면 차이가 10 이므로 2 -> 5 간선이 필요하다는 결론이 나온다.

반면 dist[2] = 12, dist[5] = 15 라면 차이가 10 이 아닌 3이므로 2 -> 5 간선은 쓰이지 않은 것이다.

 

그럼 이제 역추적은 어떤 식으로 하면 될까? 해답은 BFS 다.

Dijkstra 를 다 돌리고 난 후에는 어차피 모든 노드의 최단거리가 다 구해져있어서 위상과 상관이 없다.

 

도착점만 Queue에 넣은 후 도착점에서 시작하는 BFS 를 실시한다. (물론 역간선 graph에서)

Queue 의 front 노드와 연결된 노드들이 위에서 언급한 조건을 만족한다면, 그 간선을 chk 한다.

코드는 아래와 같다.

 

 /// traceback
queue <int> q;
memset(chk, 0, sizeof(chk)); chk[E] = 1; q.push(E);
memset(nope, 0, sizeof(nope));
while(!q.empty()){
    int now = q.front(); q.pop();
    for(auto prv : rev[now]){
        if(dist[prv.first] + prv.second == dist[now]){ /// prv.first -> now 간선이 최단거리에 포함된다
            if(!chk[prv.first]) chk[prv.first] = 1, q.push(prv.first);
            nope[prv.first][now] = 1;
        }
    }
}

 

prv.first 는 now 직전의 원소다.

dist[prv.first] + 간선 길이 == dist[now] 라면 이 간선은 최단거리에 포함된다.

BFS 이기 때문에 한 번 방문한 노드는 다시 방문할 필요가 없다. chk 를 해주면 된다.

 

결론적으로,

1. Dijsktra 를 한 번 돌린다.

2. 역간선 그래프에서 도착점으로부터 BFS 를 돌려, 최단거리에 포함되는 간선을 check 한다.

3. check 한 간선을 배제한 채 Dijkstra 를 한 번 더 돌려 답을 구한다.