백준 14221번: 편의점 (C++)

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

14221번: 편의점

---

Solved By: Dijkstra

 

시간제한이 2초인 문제였습니다. 모든 노드로부터 다익스트라를 돌린다는 설계를 하면, 시간 복잡도가 O(VElogV)라서 시간 초과가 걸릴 것이라 예상했기에 한 번의 다익스트라로 끝내야 한다 생각했습니다.

 

그래서 처음에 생각했던 건 집 노드 중 아무 노드를 골라 다익스트라를 돌려서 '편의점 노드까지의 최단 거리 - 다른 집 노드까지의 최단 거리'를 구하면 답을 구할 수 있을 거라 생각했습니다.

 

하지만, 이에는 예외가 존재합니다. '편의점 노드까지의 최단 거리 - 다른 집 노드까지의 최단 거리'가 답이 되려면 처음에 다익스트라를 돌린 집 노드에서 편의점 노드까지의 최단 거리에 포함되는 노드들 중 다른 집 노드가 반드시 포함되어야 답으로써 성립된다는 것입니다.

 

다른 풀이 방법이 떠오르지 않아 구글링을 해서 자료를 찾던 중, O(VElogV)로 통과를 한 사례들이 대부분이었습니다.

출제자의 의도가 다른 것이 있는지는 모르겠지만 아쉬운 솔루션이었습니다.

 

[궁금한 점]

그래도 찾은 자료 중 궁금한 것이 생겨 이에 대해 적어보려 합니다.

https://littlesam95.tistory.com/97

[BOJ/Gold 5] 백준 14221 편의점(C++)

 

해당 포스팅의 코드를 보면 INF값으로 초기화된 Dist 배열에 다익스트라를 여러 번 돌리는데 우려되는 부분이 '최단 거리를 제대로 갱신할 수 있는 것인가?'입니다. 

 

여러 시작점으로부터 다익스트라를 돌린 Dist배열의 최단 거리 값들은 어떤 시작점으로부터 나온 최단 거리 값인지 알 수 없습니다.

 

다만, A(시작점 set), B(도착점 set) (A와 B에 겹치는 노드는 없다)라는 가정이 주어지면, A의 모든 노드에서 B의 모든 노드로 가는 최단 경로들은 구할 수 있습니다. 그 아이디어를 가지고 포스팅의 코드를 구현한 것입니다.

 

그러므로 여러 시작점들로부터 어떤 도착점까지의 거리가 최단 거리인지는 알 수 있습니다. 기존의 Dist값보다 작은 값들만 갱신하는 것이 Dijkstra의 메커니즘이기 때문에 문제의 요구 사항에는 적합합니다.

 

그럼 반대로 시작점을 편의점으로 두어야 어떤 집(도착점)이 최단 거리를 가지는지 알 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 5001
#define INF 1e9
#define pii pair<int, int>
using namespace std;

int n, m;
vector<pii> adj[MAX];
vector<int> en;
bool st[MAX];
int dist[MAX];

struct cmp{
    bool operator()(pii&a, pii&b){
        return a.second > b.second;
    }
};

void dijkstra(int node){
    dist[node] = 0;
    priority_queue<pii, vector<pii>, cmp> pq;
    pq.push({node, 0});
    
    while(!pq.empty()){
        int now = pq.top().first;
        int nowCost = pq.top().second;
        pq.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].first;
            int nextCost = adj[now][i].second;
            
            if(nowCost + nextCost < dist[next]){
                dist[next] = nowCost + nextCost;
                pq.push({next, dist[next]});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int v, u, w; cin >> v >> u >> w;
        adj[v].push_back({u, w});
        adj[u].push_back({v, w});
    }
    
    int p, q; cin >> p >> q;
    for(int i = 0; i < p; i++){
        int v; cin >> v;
        st[v] = true;
    }
    
    for(int i = 0; i < q; i++){
        int v; cin >> v;
        en.push_back(v);
    }
    
    fill(dist, dist+MAX, INF);
    for(int i = 0; i < en.size(); i++){
        dijkstra(en[i]);
    }
    
    int shortestPath = INF;
    int ans = 0;
    
    for(int i = 1; i <= n; i++){
        if(st[i] && dist[i] < shortestPath){
            shortestPath = dist[i];
            ans = i;
        }
    }
    
    cout << ans;
    return 0;
}