[백준][C++] 13911 집 구하기

www.acmicpc.net/problem/13911

13911번: 집 구하기

 

 

 

알고리즘 종류

다익스트라

 

 

 

사고 과정

다익스트라는 한 정점에서 모든 정점으로 가는 최단거리를 구하는 알고리즘입니다. 이 문제에서는 많은 맥도날드에서 모든 집으로 가는 최다거리와 많은 스타벅스에서 모든 집으로 가는 최단거리의 합을 구하는 문제이다. 많은 맥도날드와 많은 스타벅스를 어떻게 하나의 정점으로 처리할 수 있을까요? 

 

비용이 없는 가상의 맥도날드 노드 한 개와 가상의 스타벅스 노드 한 개를 만들면 해결할 수 있습니다. 가상의 맥도날드 노드 9과 가상의 스타벅스 노드 10를 만들어 주었습니다. 그러면 9번과 10에서 다익스트라 알고리즘을 사용하면 됩니다.

 

 

 

구현(C++)

#include <iostream>
#include <queue>
#include <vector>
#define MAX 987654321
 
using namespace std;
 
int n, e, m, s;
int mx, sy;
int node;
 
 
int dist[2][10010];
vector<vector<pair<int, int> > > edges;
vector<int> house;
 
 
void dijkstra(int start, int state){
    for(int i=0; i<n+5; i++) dist[state][i] = MAX;
    
    priority_queue<pair<int, int> > pq;
    pq.push({0, start});
    
    while(!pq.empty()){
        int here = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        
        if(dist[state][here] < cost) continue;
        
        for(int i=0; i<edges[here].size(); i++){
            int next = edges[here][i].first;
            int next_cost = cost + edges[here][i].second;
            
            // 제시된 y와 x보다 크면 수행하지 않는다.  
            if(state==0 && next_cost > mx) continue;
            else if(state==1 && next_cost > sy) continue;
            
            if(dist[state][next] > next_cost){
                dist[state][next] = next_cost;
                pq.push({-next_cost, next});
            }
        }
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> e;
    edges.resize(n+5);
    house.resize(n+5);
    
    int u, v, w;
    for(int i=0; i<e; i++){
        cin >> u >> v >> w;
        edges[v].push_back({u, w});
        edges[u].push_back({v, w});
    }
    
    cin >> m >> mx;
    for(int i=0; i<m; i++){
        cin >> node;
        edges[n+1].push_back({node, 0}); 
        house[node] = -1;
    }
    
    cin >> s >> sy;
    for(int i=0; i<s; i++){
        cin >> node;
        edges[n+2].push_back({node, 0});
        house[node] = -1;
    }
 
 
    dijkstra(n+1, 0); // 맥도날드 시작
    dijkstra(n+2, 1); // 스타벅스 시작
    
    
    int answer = MAX;
    for(int i=1; i<=n; i++){
        if(house[i] == -1) continue; // 집일 때만 최소 거리 합 계산하기  
        
        int sum = dist[0][i] + dist[1][i];
        if(answer > sum) answer = sum;
    }
    
    if(answer == MAX) cout << - 1;
    else cout << answer << endl;
    
}
 

 

 

 

시행착오

첫 번째 시도는 시간초과가 발생했습니다. 모든 맥도날드와 스타벅스에서 다익스트라를 수행했습니다. 이미 시간초과가 날 것을 시간복잡도를 통해서 알고 있었지만 방법이 생각나지 않아서 시도는 해보았습니다. 이후에 이 분의 블로그에서 방법을 알 수 있었습니다. 더미노드를 생성한다는 것을 정말로 획기적인 아이디어라고 생각했습니다. 더미노드를 사용하면 같은 종류의 많은 노드에서 모든 노드로 가는 방법을 깔끔하게 해결할 수 있습니다. 같은 종류의 많은 노드를 더미노드로 하나로 묶고 다익스트라를 수행하면 되기 때문입니다.