백준 5719번 - 거의 최단 경로

www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

다익스트라 알고리즘 관련 문제이다.

 

처음 봤을 때 어떻게 해야 할지 감은 잡혔으나 그걸 코드로 옮기는 게 너무 어려웠다..

 

먼저 떠올렸던 해법은

 

1. 다익스트라를 통해 시작점부터 도착점까지 최단 거리를 구한다.

2. 최단 경로에 포함된 간선들을 모두 제거한다.

3. 다익스트라를 통해 거의 최단 경로를 구한다.

 

문제는 2번이였다.

 

최단 경로가 여러 개가 나올 수 있고, 그렇다면 그 해당 간선들을 어떻게 제거해줘야 할까?

 

플래티넘 문제이기도 하고 다익스트라 알고리즘 자체가 어려워 빠르게 포기하고 구글링 해본 게 살짝 아쉽긴 하다..

(저는 Crocus님 블로그를 참고했습니다만 최대한 쉽게 제 생각대로 다시 코드를 짠 거라 조금 다를 수 있어요!)

 

생각보다 간단한 방법이 있다.

 

바로 BFS를 통해 제거해주면 된다!

 

먼저 다익스트라를 통해 최단 경로의 간선들이 담긴 인접 행렬(결국 그래프)을 만들어주고, BFS, 즉 그래프 완전 탐색을 통해 새롭게 만들어진 인접 행렬(그래프)을 돌며 모든 간선들을 제거해준다.

 

이제 어떻게 풀어야 하는지 알았으면 바로 코드로 작성하면 되는데 여기서 약간의 함정들이 있다.

 

함정 1. 

 

최단 경로의 간선들이 담긴 인접 행렬(그래프)을 만들어 줄 때 반드시 역 방향으로 만들어주어야 한다!

 

이게 뭔 소린가..? 어느 블로그에서도 왜 역방향만 되는지 알려주지 않네요..

 

B.U.T 그러나! 생각해보면 정말 당연한 이야기였다.

 

천천히 살펴보자.

 

문제의 예제를 보자.

 

여기서 역 방향으로 만들어 주어야 한다는 말은 새롭게 만들어진 그래프가 다음과 같아야 한다는 말이다.

 

역방향 그래프

 

같은 최단 경로이긴 하나 이 그래프의 시작점이 문제의 도착점이 된다.

 

왜 이렇게 해야 할까?

 

나도 처음엔 반항심? 반 궁금증 반으로 순방향 그래프를 만들려고 생각했었다.

 

하지만 만약 순방향 그래프로 만든다면 아래와 같은 그래프가 만들어질 것이다.

 

순방향 그래프

사실 당연한 이야기이다.

 

다익스트라 알고리즘 자체가 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 것이다.

 

새롭게 그래프를 만들 시 다른 모든 정점들의 최단 경로도 포함하게 된다는 점이다.

 

그럼 만약 순방향으로 만든 인접 행렬에 bfs를 돌리면 어떻게 될까?

 

당연히 시작점을 처음에 큐에 넣고 돌릴 것이고, 그렇게 되면 위에 표시된 빨간색 간선들이 모두 지워질 것이다.

 

그렇다면 지워지면 안 되는 간선들까지 지워지게 된다. (위의 그림에선 점선인 간선이 해당됨)

 

그럼 역방향은?

 

역방향 그래프에서는 도착점부터 bfs를 실행할 것이고 그렇다면 반드시 최단 경로에 포함된 간선만 지우게 된다.

 

(한번 위의 '역방향 그래프'와 '순방향 그래프'에서 직접 bfs를 그려보세요! 이해하기 어렵지 않아요!)

 

 

이건 당연히 bfs를 사용할 때 해당하는 문제점이다.

(지금 이렇게 글을 쓰면서 느낀 점인데 굳이 bfs를 안 돌려도 해당 간선이 최단경로에 포함되었는지 안되었는지만 알고 있다면 해결할 수 있을 것 같기도 한데..)

 

어쨌든 순방향으로 하면 안 됨!!

 

 

 

함정 2. 

 

아.. 이건 솔직히 함정이라고 해야 되나 짜증 유발 요소라 해야 되나 모르겠지만

 

이 문제의 코드를 짜다보면 새로운 그래프를 만들어줄 때 문제가 생긴다.

 

예를 들어 원래 최단 경로에 포함된 간선을 가지고 있다가 새로운 최단 경로를 찾았다고 생각해보자.

 

그럼 기존 최단 경로는 최단 경로가 아닌 것이 확실하기 때문에 저장해 놓았던 간선들을 전부 지워줘야 한다.

 

나는 이 간선들을 vector를 사용한 인접 행렬로 가지고 있었기 때문에 해당 vector[vertex]를 비워주고 다시 새로운 간선들을 넣어줘야 한다.

 

이때 vector.clear() 함수를 사용하게 되는데 여기서 문제가 생긴다.

 

코드를 다 짜 놓고 테스트해보는데 출력이 안되고 비정상적으로 종료가 되었다.

 

뭐 이 정도야 늘 있는 일이니 바로 디버깅해보니 바로 저 부분, vector.clear() 부분에서 비정상적 종료가 되는 것이다!

 

이런 경우는 처음이라 더 자세히 살펴보니 무슨 인자를 정확히 넘기지 않았다는 둥.. 

 

어쨌든 내가 이해할 수 없는 오류가 생겼다.

 

계속해서 구글링 한 결과는 그냥 vector.clear()가 문제가 생길 수 있다...

 

도저히 해결되지가 않아서 정말 혹시나, 혹시나 해서 온라인 컴파일러에 돌려보니 제대로 실행되었다.

 

아........  

 

그래서 그냥 백준에 제출해보니 맞았다.....

 

그래서 결론은 그냥 제출하세요.....

 

 

 

이렇게 두 가지 함정만 잘 피한다면 문제를 해결할 수 있다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
 
vector<pii>g[505];
int dis[505];
vector<int>way[505];
bool check[505];
 
void dijkstra(int x) {
    dis[x] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(make_pair(0, x));
    while (!pq.empty()) {
        int now = pq.top().second;
        int wei = pq.top().first;
        pq.pop();
        if (dis[now] < wei) continue;
        for (int i = 0; i < g[now].size(); i++) {
            if (g[now][i].second == -1)continue;// 두 번째 dijkstra에서 제거된 간선 제외!
            int next = g[now][i].first;
            int ww = g[now][i].second;
            if (dis[now] + ww < dis[next]) {
                dis[next] = dis[now] + ww;
                way[next].clear(); 
                way[next].push_back(now); // 최단 경로 갱신
                pq.push(make_pair(dis[next], next));
            }
            else if (dis[now] + ww == dis[next]) {
                way[next].push_back(now); // 반드시 이렇게 next와 now를 설정해야 함!
            }
            else continue;
        }
    }
}
 
void bfs(int x) {
    queue<int>q;
    q.push(x);
    while (!q.empty()) {
        x = q.front();
        q.pop();
        if (check[x] == true) continue;
        check[x] = true;
        for (int i = 0; i < way[x].size(); i++) {
            int nx = way[x][i];
            for (int j = 0; j < g[nx].size(); j++) {
                if (g[nx][j].first == x) g[nx][j].second = -1; // 간선을 삭제
            }
            q.push(nx);
        }
    }
}
 
void init() {
    memset(g, 0, sizeof(g));
    memset(way, 0, sizeof(way));
    memset(dis, 127, sizeof(dis));
    memset(check, false, sizeof(check));
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    while (1) {
        int n, m, start, end, u, v, e;
        init(); // 초기화 시켜주기
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        cin >> start >> end;
        for (int i = 0; i < m; i++) {
            cin >> u >> v >> e;
            g[u].push_back(make_pair(v, e));
        }
        int INF = dis[0];
        dijkstra(start); // start부터 모든 정점까지의 최단 거리 구함
        bfs(end); // end부터 start까지 연결된 간선들을 제거
        memset(dis, 127, sizeof(dis)); // 최단 거리를 다시 구해야 하므로
        dijkstra(start); // 다시 최단 거리 구함
        if (dis[end] == INF) cout << -1 << "\n";
        else cout << dis[end] << "\n";
    }
}

 

추가적으로 테스트 케이스가 있는 문제이기 때문에 사용하는 배열들의 초기화를 잘 해주자!