boj 11779번 문제를 통해 다시보는 경로복원 방법에 대해서.

일단 다익스트라 알고리즘을 통해서 경로 복원을 할때는 플로이드 알고리즘을 통해서 경로 복원을 하는것과 매우 유사한데, 

이때에 pre[ ] 배열을 선언해주어서, 새로운 경로로 값을 갱신할때마다 pre 배열에 어디로부터 경로를 이어서 갱신되게 되었는지를

남긴다면 나중에 그 pre 배열을 거꾸로 타고 따라 가다보면 역순으로 경로를 파악할 수 있고, 그걸 vector에 담아서 reverse 함수를 사용하면, 시작부터 끝으로 향하는 형태로 다시 경로를 뒤집어서 나타낼 수 있다. 

    while(!pq.empty()){
        auto cur=pq.top(); pq.pop();
        if(d[cur.second]!=cur.first) continue;
        for(auto nxt: adj[cur.second]){
            if(d[cur.second]+nxt.first>=d[nxt.second]) continue;
            d[nxt.second]=d[cur.second]+nxt.first;
            pq.push({d[nxt.second],nxt.second});
            pre[nxt.second]=cur.second; //<<=== 바로 여기!
        }
    }

코드 내부에 생성한 것처럼 일반적으로 다익스트라를 구현할때, 갱신해주는 부분에 pre 배열값도 같이 갱신해주면서 어디로부터 오게 된것인지에 대해서 기록하고, 

    vector<int> path;
    int cur=en;
    while(cur!=st){
        path.push_back(cur);
        cur=pre[cur];
    }
    path.push_back(cur);//st 가 된 cur 값을 담아주기. 위에서 안담기기 때문에. 
    reverse(path.begin(),path.end());
    cout<<path.size()<<'\n';
    for(auto x: path) cout<<x<<' ';

이러한 형태로 코드를 작성하면, 현재로부터 과거로 한칸 한칸씩 따라 들어가게 되면서 그 값들이 vector path에 담기고, 

이때에 cur== st가 되는 경우는 while문 내부가 실행되지 않기 때문에 마지막에 따로 st와 같아진 cur 값을 담아주면서 문제에서 요구하는

st와 en 지점까지 모두 담게 만들 수 있었다. 

그리고 이걸 reverse 함수를 통해서 vector의 순서를 뒤집어 주었다. 

 

현재 일반적으로 플로이드를 돌린다던지, 다익스트라를 구현하는 과정은 꽤 잘 이해했는데, 그 과정에서 경로복원의 경우는 아직 익숙하게 구현해내지 못하는것 같다.

 이 문제의 경우도 지속적으로 다시 풀어보면서 연습해보도록 하자. 그리고 이 방법에 대한 이해를 우선적으로 더욱 노력해서 해보도록 하자.