[백준 14221] 편의점

문제 풀이

 

편의점의 후보와 집의 후보가 나열되는데, 이때 우리는 편의점이랑 가까운 집을 찾으려고 한다.

어떻게 찾을 수 있을까?

 

편의점으로부터 가까운 집을 고르는 것이기 때문에 이는 최단 경로를 구해야 된다.

그런데 그러한 경로는 다양하기 때문에 이러한 것들을 빠르게 찾아낼 수 있는 것이 바로 다익스트라다.

한 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있기 때문이다.

 

여기서 핵심은 역발상이다.

집이라는 후보가 정해져 있기 때문에 해당 편의점을 시작 지점으로 잡은 다음 출발하여 집의 후보를 발견했다면 그때의 경로와 집의 번호를 pair로 정답 배열에 저장한다. 이렇게 저장된 정답 배열을 오름차순으로 정렬하면 우리가 구하고자 하는 답이 나오게 된다.

 

시간 복잡도를 생각해보자.

다익스트라를 인접 리스트로 구현했다면 O(ElogV)다.

모든 편의점에서부터 다익스트라를 구하기 때문에 O(q x ElogV) = O(5,000 x 100,000 x log5,000)

얼핏 보면 시간이 빡빡한데, 통과했다. 아마 테케가 더 빡빡하게 주어지면 재채점시에 틀릴 수도 있을 것 같다.

더 빠른 풀이를 보니까 하나의 시작점에서 생각하는 게 아니라 여러 시작점(편의점을 시작점으로 해서 편의점의 수만큼 우선순위 큐에 넣고 돌리는 것이다.)

 

소스 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 5000 + 1;
const int INF = 2e9;
typedef pair<int, int> pii;

int n, m, p, q;
vector<pii> adj[MAX];
vector<int> houses, shops;
vector<pii> ans;

void dijkstrea(int start)
{
    vector<int> dist(n + 1, INF);
    priority_queue<pii> pq;
    pq.push({0, start});
    dist[start] = 0;
    while(!pq.empty())
    {
        int cur = pq.top().second;
        int distance = -pq.top().first;
        pq.pop();
        
        if(dist[cur] < distance) continue;
        for(int i = 0; i < adj[cur].size(); i++)
        {
            int next = adj[cur][i].first;
            int nextDistance = adj[cur][i].second + distance;
            if(dist[next] > nextDistance)
            {
                dist[next] = nextDistance;
                pq.push({-nextDistance, next});
            }
        }
    }
    
    for(int house : houses)
    {
        if(dist[house] != INF)
            ans.emplace_back(dist[house], house);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }
    
    cin >> p >> q;
    houses.resize(p);
    shops.resize(q);
    for(int i = 0; i < p; i++) cin >> houses[i];
    for(int i = 0; i < q; i++) cin >> shops[i];
    // 편의점에서 출발해서 각 집의 후보지를 탐색한 후 정답 배열에 넣어준다.
    for(auto start : shops)
    {
        dijkstrea(start);
    }
    
    sort(ans.begin(), ans.end());
    cout << ans[0].second << endl;
    return 0;
}