백준 1916번:최소비용 구하기

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

1916번: 최소비용 구하기

 

이 문제는 다익스트라 문제이다.

하지만 ! 

기존에 하던 다익스트라 방식으로는 시간초과가 난다..

그래서 왜지... 라는 의구심을 가지고 생각을 해봤다..

 

아래가 시간초과가 난 코드다 .

이 코드의 잘못된 점을 찾아보면 방문된 점의 처리가 제대로 안되어 있다는 것이다.

인접한 점의 노드의 간선들을 모두 우선순위 큐에 넣는 방식이다.

이때 이미 방문했던 노드들은 굳이 for문을 돌릴 필요가 없다 . 하지만 아래는 불필요하게 for문이 돌아가고 있고 여기서 시간이 초과가 되는 것이다.  

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF 987654321
int n,m;
int start,e;
int dist[1001];
bool check[1001];
vector<pair<int,int>> arr[1001];
void dijkstra(int start){
    dist[start]=0;
    priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({dist[start],start});
    while(!q.empty()){
        int distNow = q.top().first;
        int node = q.top().second;
        q.pop();
        check[node] = true;
        for(int i=0;i<arr[node].size();i++){
            int distNext = arr[node][i].first;
            int nodeNext = arr[node][i].second;
            if(!check[nodeNext] && dist[nodeNext]> dist[node]+distNext){
                dist[nodeNext] = dist[node] + distNext;
                q.push({dist[nodeNext],nodeNext});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        arr[a].push_back({c,b});
    }
    for (int i = 1; i <= n; i++) 
		dist[i] = INF;
    cin>>start>>e;
    dijkstra(start);
    cout << dist[e];
}

 

 

그럼 개선된 코드를 보자

이 코드와 위의 코드의 차이는 

if(check[node]) continue;

즉 이미 방문했던 노드는 for문을 안돌리게 하는 것이다. 불필요한 반복문은 지우자.. 

이렇게 하면 시간 복잡도  n log(e)가 되는 것이다. (n은 정점 ,e는 간선)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF 987654321
int n,m;
int start,e;
int dist[1001];
bool check[1001];
vector<pair<int,int>> arr[1001];
void dijkstra(int start){
    dist[start]=0;
    priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({dist[start],start});
    while(!q.empty()){
        int distNow = q.top().first;
        int node = q.top().second;
        q.pop();
        if(check[node]) continue;               //코드 추가
        check[node] = true;
        for(int i=0;i<arr[node].size();i++){
            int distNext = arr[node][i].first;
            int nodeNext = arr[node][i].second;
            if(!check[nodeNext] && dist[nodeNext]> dist[node]+distNext){
                dist[nodeNext] = dist[node] + distNext;
                q.push({dist[nodeNext],nodeNext});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        arr[a].push_back({c,b});
    }
    for (int i = 1; i <= n; i++) 
		dist[i] = INF;
    cin>>start>>e;
    dijkstra(start);
    cout << dist[e];
}

 

이제 인터넷에 잘 알려진 코드를 보자.

 

이 코드는 방문노드를 생성하지 않고 

if(dist[node]<distNow) continue;

이 코드를 추가 하면 된다. 이 코드는 시작 점부터 현 node 까지의 최소 거리가  간선으로 등록된 거리보다 작으면 탐색을 안한다.

그 이유는 이미 최소거리가 선정이 되었기때문이다. (이해가 안가면 다익스트라의 최소 간선 크기부터 선택하고 올라가는 것을 잘 생각해보자)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF 987654321
int n,m;
int start,e;
int dist[1001];
vector<pair<int,int>> arr[1001];
void dijkstra(int start){
    dist[start]=0;
    priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({dist[start],start});
    while(!q.empty()){
        int distNow = q.top().first;
        int node = q.top().second;
        q.pop();
        
        if(dist[node]<distNow) continue;    //이거 추가 + 방문 노드 탐색 안함
        for(int i=0;i<arr[node].size();i++){
            int distNext = arr[node][i].first;
            int nodeNext = arr[node][i].second;
            if( dist[nodeNext]> dist[node]+distNext){
                dist[nodeNext] = dist[node] + distNext;
                q.push({dist[nodeNext],nodeNext});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        arr[a].push_back({c,b});
    }
    for (int i = 1; i <= n; i++) 
		dist[i] = INF;
    cin>>start>>e;
    dijkstra(start);
    cout << dist[e];
}