BOJ 5791 거의 최단 경로

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

5719번: 거의 최단 경로

다익스트라 알고리즘으로 최단 경로(거리!)를 찾고, 최단 경로를 지운 후 다시 다익스트라를 호출해 거의 최단 경로를 찾는 방법으로해결했다. (쉽죠?)

 

문제는 구현에 있었는데.. 그래프를 주로 vector of vector 형태의 인접 리스트로 작성하는데 거의 다 작성했을 즈음 돼서 문제가 발생했다. 

 

문제의 조건에서

거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

이 조건 때문인데, 크게 두 가지 경우에 대해 미처 생각하지 못해 문제가 발생했다.

    1) 최단 경로들을 지우기 위해 탐색할 때 발생하는 인접 리스트의 구조적 한계

    2) 최단 경로가 여러개 있을수도 있지만, 1차원 배열에 최단 경로를 저장 (prev[u] = v와 같은 형태로)

 

방문중인 정점과 인접한 정점들을 탐색하는데 걸리는 시간복잡도를 조금이라도 줄이고자 하는 마음에서 인접 리스트를 선호하는데, 이 문제의 경우 최단 경로를 지우기 위해 최단경로의 목적지 -> 출발지 순으로 그래프를 거꾸로 탐색해야 한다. 문제는 여기서 발생했다.

(현재 방문중인 정점: //(u//), 인접한 부모 정점들 //(v_{k}//)라 할때)

인접 행렬을 이용할 때에는 mat[//(v_{k}//)][//(u//)] 와 같이 O(1) 시간에 각 정점의 조건을 확인할 수 있지만(총 O(N)), 인접 리스트의 경우 각 부모 정점에 인접한 모든 정점들 중에 현재 방문하는 u가 있는지에 대해 매번 끝까지 탐색해야 하기 때문에 총 O(N^2) 의 시간복잡도가 필요하다.

 

물론 인접 리스트를 이용하면서 문제를 해결한 방법은 있지만, 발생한 문제들과 이후 코드 추가로 인해 생길 복잡성을 생각하면 그냥 인접 행렬로 다시 작성하는게 낫겠다는 결론에 도달했고 결과는 다음과 같다.

---

u.w: 현재 탐색하는 경로의 방문하는 정점까지의 거리, mat[i][j]: i -> j 정점까지의 거리를 의미

#include <iostream>
#include <queue>
#include <cstring>

int mat [502][502];

struct Edge {int vt,w;
    bool operator<(const Edge& a) const { return w > a.w; }
    Edge() = default;
    Edge(int n, int w) : vt(n), w(w) {}
};
int N,E,Dst;

using namespace std;

void dijkstra(int d[],int s) {
    fill(d,d+N,INT32_MAX);
    priority_queue<Edge> PQ;
    d[s] = 0; // 시작 정점까지 거리 0으로
    PQ.push({s,0});
    while(!PQ.empty()) {
        Edge u = PQ.top();
        PQ.pop();
        if(d[u.vt] < u.w) continue; 
        // 현재 u까지의 거리 u.w가 최단 거리 d[i]보다 크면 방문할 필요 없음.
        for(int i=0;i<N;i++) {
            if(mat[u.vt][i] <= 0) continue; 
            // 경로가 없거나(0) 인접한 경로가 최단 경로(-1)이면 무시
            int nDist = mat[u.vt][i] + u.w, nVt = i;
            if(d[nVt] > nDist) {
                d[nVt] = nDist; // 인접한 정점 까지의 거리 업데이트
                PQ.push({nVt,nDist}); // 방문할 정점으로
            }
        }
    }
}

void erase(int d[]) {
    // 도착 정점부터 최단 경로들을 따라 거꾸로 올라가며 최단 경로 그래프에서 삭제(방문하지 않도록)
    queue<int> Q;
    Q.push(Dst); // 도착 정점부터
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int i=0;i<N;i++) {
            if(mat[i][u] > 0 && d[i] + mat[i][u] == d[u]) { 
            // 거꾸로 올라가며 i에서 현재 방문중인 정점(u)까지의 거리가 최단 경로이면
                mat[i][u] = -1; // 최단 경로임을 표시
                Q.push(i); // 거꾸로 올라가며 위 동작 반복
            }
        }
    }
}

int main() {
    while(1) {
        scanf("%d%d",&N,&E);
        if(N+E == 0) return 0;
        int d[N], s;
        scanf("%d%d",&s,&Dst);
        
        for(int i=0;i<N;i++)
            memset(mat[i],0,sizeof(mat[i]));
            
        for(int i=0;i<E;++i) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            mat[u][v] = w;
        }
        dijkstra(d,s); // 최단 경로를 찾기 위한 탐색
        
        erase(d); // 최단 경로 삭제
        
        dijkstra(d,s); // 거의 최단 경로 탐색
        
        printf("%d\n",d[Dst]==INT32_MAX?-1:d[Dst]);
    }
}

---

번외로, 맨 끝에 0 0이 주어지는 TC의 경우, 입력을 받고 a+b == 0인지 확인을 했지만

while(scanf("%d%d",&a,&b), (a||b))

와 같이 입력을 받을 수도 있다.