boj 1238 번 문제를 통해 보는 다익스트라와 왕복 거리.

처음에 왕복 거리를 계산하는걸, 플로이드로 하기에는 노드의 수가 많아서 시간초과가 발생할것이라는 생각에, 다익스트라를 활용해서

왕복 거리를 반대 방향으로 다시 다익스트라 알고리즘을 활용해서 구할 생각을 하고, 다익스트라 구현 부분을 함수로 넘긴뒤에 그걸 시작과 끝을 바꿔서 시행하는걸 떠올려서 구현하였다. 

#include <bits/stdc++.h>
using namespace std;

int n , m ,x;
vector<pair<int,int>> adj[1'005];
int d[1'005];
const int INF= 0x3f3f3f3f;

int dijkstra(int a, int b){
    fill(d,d+1+n,INF);
    
    priority_queue< pair<int,int>,
                    vector<pair<int,int>>,
                    greater<pair<int,int>>> pq;

    d[a]=0;
    pq.push({d[a],a});
    while(!pq.empty()){
        auto cur= pq.top(); pq.pop();
        if(d[cur.second]!=cur.first) continue;
        for( auto nxt: adj[cur.second]){
            if(d[nxt.second]<= d[cur.second]+nxt.first)  continue;
            d[nxt.second]= d[cur.second]+nxt.first;
            pq.push({d[nxt.second],nxt.second});
        }
    }
    return d[b];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>x;
    while(m--){
        int u, v, w;
        cin>>u>>v>>w;
        adj[u].push_back({w,v});
    }

    int ans=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            ans=max(ans,dijkstra(i,j)+dijkstra(j,i));
        }
    }
    cout<<ans;
}

가장 먼저 떠올린 것은 이중 for문 형태로 구현해서 저중에서 가장 ans가 큰 것을 찾는 형태로 코드를 작성하였다.

그런데 제출하니까 시간 초과가 났다. 

그래서 풀이를 참고해보니 

 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>x;
    while(m--){
        int u, v, w;
        cin>>u>>v>>w;
        adj[u].push_back({w,v});
    }

    int ans=0;
    for(int st=1; st<=n; st++)
        ans=max(ans, dijkstra(st,x)+dijkstra(x,st));
    cout<<ans;
}

이런식으로 해서 차수를 2차 for문에서 1차 for문으로 줄일 수 있는 형태가 있었다. 

생각해보니 저렇게 처음처럼 이중 for문을 활용하면 내가 원하는 것은 문제에서 x 로 주어진 한 점에서 다른 점들가지의 왕복인데, 

이중 for문을 하면 다른 불필요한 곳까지 갔다가 다시 돌아오는 경우까지 계산을 해야 하는 경우가 되었다. 

그렇게 되면 대략적으로 1000까지 최대의 경우라 생각할때, 1000개의 경우를 보면 되는 걸 1'000'000 개의 경우를 계산해서 답을

구하는 꼴이 되어버린다. 문제에서 주어지는 x 값을 이용해서 이렇게 1중 for문으로 바꾸어서 왕복 거리를 계산할 수 있는데 그렇게 불필요한 연산을 할 필요가 없다. 

다음에는 이렇듯 왕복거리를 계산할때, 특정한 한 점에 대해서 구해야 하는 경우는 이중for문 형태로 만들지 말고, 1중 for문으로 해결할 수 있다는걸 떠올리고 그렇게 만들어 보기 위해서 노력해보자. 

그런데 저 부분을 제외하고는 전반적으로 로직도 잘 짜고 다익스트라 코드도 잘 짰다. 이 문제의 경우 다음에도 풀어보면서 이렇게 왕복거리를 구하는 경우 다익스트라를 활용해서 어떤식으로 코드로 옮길지에 대해서 다시 한번 생각해보고 공부해보자.