백준(BOJ) 13911 집 구하기 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/13911

13911번: 집 구하기

문제 풀이에 사용된 알고리즘: 다익스트라, 최단 경로, 더미 노드

 

문제에서 제시하는 조건(맥세권인지, 스세권인지)를 만족하는 정점(집)들 중에서, (맥도날드까지의 거리) + (스타벅스까지의 거리)가 작은 수치를 보이는 집을 찾는 문제이다.

 

우선 노드의 수가 굉장히 많고, 인접 행렬이 아닌 간선 형태의 인접 리스트가 주어지기 때문에 다익스트라 알고리즘을 적용하기로 하였다.

 

최초, 스타벅스와 맥도날드의 좌표를 macs, stars라는 컨테이너에 저장해둔다. 그리고 하나 하나의 집들에 대해서 다익스트라를 돌며, 맥도날드와 스타벅스 좌표를 컨테이너에서 하나씩 접근하며 맥세권과 스세권 모두 만족하는 경우에만, 맥도날드와 스타벅스까지의 거리를 합하여 ans라는 정답용 변수의 최소값을 찾는 방식을 이용하였다.

 

pq를 사용하는 다익스트라가 경로 알고리즘 중에서는 빠른 속도를 보인다고 하지만 최대 1만개나 되는 점들에 대해서 모두 다익스트라 알고리즘을 돌리는 부분에서 시간 초과가 발생하였다.

 

집에 대해서 다익스트라 알고리즘을 적용하지 않고, 맥도날드나 스타벅스를 시작점으로 한다고 하여도 맥도날드와 스타벅스 또한 각각 최대 9998개가 존재하므로 시간초과가 발생할 수 밖에 없다.

 

그래서 검색을 통해서 "더미 노드"라는 개념을 알게 되었고 적용했는데 다음과 같다. (다익스트라 알고리즘을 이해하고 계신 분들을 대상으로 간략히 설명을 적은 것입니다.)

 

모든 맥도날드와 0의 거리가 0인 어떤 맥도날드(M)가 존재한다면, M을 시작점으로 다익스트라를 한 번만 적용하여도 각 집에서 가장 가까운 맥도날드까지의 거리를 파악할 수 있다.

 

즉, 맥도날드에 대해서만 최대 9998번 다익스트라 알고리즘을 적용해야 했던 문제가, 단 한번의 다익스트라를 적용하는 문제로 변경될 수 있다!

 

이런 M을 더미 맥도날드라고 하고, 스타벅스에 대해서도 동일한 원리의 S를 지정해줄 수 있다.

 

위의 개념을 알고 나면, 조금 다양한 변수를 추가하여 구현만 하면 문제를 쉽게 해결할 수 있다. 보다 상세한 내용은 코드의 주석을 참고하면 이해에 도움이 될 수 있을 것 같다.

 

/* BOJ 13911 집 구하기 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
const int INF = 1e9;
int v, e, dist[10003][2], m, s, x, y;
bool visited[10003], is_house[10003], is_mac_or_star[10003][2];
vector<pair<int, int>> edges[10003];
vector<int> macs, stars;
int dummy_mac, dummy_star;
 
struct cmp
{
    bool operator()(pair<int, int> p1, pair<int, int> p2)
    {
        return p1.second > p2.second;
    }
};
 
void dijkstra_mac(int start) // 맥도날드용 다익스트라
{
    memset(visited, 0x00, sizeof(visited));
    for (int i = 1; i <= v; i++)
        dist[i][0] = INF;
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    pq.push({ start, 0 });
    dist[start][0] = 0;
 
    while (!pq.empty())
    {
        int cur = pq.top().first, distance = pq.top().second;
        pq.pop();
 
        if (visited[cur])
            continue;
 
        visited[cur] = true;
 
        for (auto edge : edges[cur])
        {
            int next = edge.first, cost = edge.second;
 
            if (distance + cost < dist[next][0])
            {
                dist[next][0] = distance + cost;
                pq.push({ next, dist[next][0] });
            }
        }
    }
}
 
void dijkstra_star(int start) // 스타벅스용 다익스트라 
{
    memset(visited, 0x00, sizeof(visited));
    for (int i = 1; i <= v; i++)
        dist[i][1] = INF;
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    pq.push({ start, 0 });
    dist[start][1] = 0;
 
    while (!pq.empty())
    {
        int cur = pq.top().first, distance = pq.top().second;
        pq.pop();
 
        if (visited[cur])
            continue;
 
        visited[cur] = true;
 
        for (auto edge : edges[cur])
        {
            int next = edge.first, cost = edge.second;
 
            if (distance + cost < dist[next][1])
            {
                dist[next][1] = distance + cost;
                pq.push({ next, dist[next][1] });
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> v >> e;
    for (int i = 1; i <= v; i++)
        is_house[i] = true;
 
    for (int i = 0; i < e; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back({ v,w });
        edges[v].push_back({ u,w }); // 양방향 통행 가능
    }
    
    // 더미 맥도날드, 더미 스타벅스
    // 더미 맥도날드는 모든 맥도날드와의 거리가 0인 맥도날드
    // 더미 스타벅스는 모든 스타벅스와의 거리가 0인 스타벅스
    // 기존에 존재하는 v개의 노드와의 간섭을 피하기 위해 v + 1, v + 2 인덱스 사용
    dummy_mac = v + 1, dummy_star = v + 2;
 
    // 맥도날드 정보 입력 받기
    cin >> m >> x;
    for (int i = 0; i < m; i++)
    {
        int a;
        cin >> a;
        is_house[a] = false;
        // 더미 맥도날드와 진짜 맥도날드 간 간선 연결
        edges[dummy_mac].push_back({ a, 0 });
        edges[a].push_back({ dummy_mac, 0 });
    }
 
    // 스타벅스 정보 입력받기
    cin >> s >> y;
    for (int i = 0; i < s; i++)
    {
        int a;
        cin >> a;
        is_house[a] = false;
        // 더미 스타벅스와 진짜 스타벅스간 간선 연결
        edges[dummy_star].push_back({ a, 0 });
        edges[a].push_back({ dummy_star, 0 });
    }
 
    // 맥세권 조사
    dijkstra_mac(dummy_mac);
    for (int i = 1; i <= v; i++)
    {
        if (!is_house[i])
            continue;
 
        if (dist[i][0] <= x) // 맥세권
            is_mac_or_star[i][0] = true;
    }
 
    // 스세권 조사
    dijkstra_star(dummy_star);
    for (int i = 1; i <= v; i++)
    {
        if (!is_house[i])
            continue;
 
        if (dist[i][1] <= y) // 스세권 
            is_mac_or_star[i][1] = true;
    }
 
    int ans = INF;
    for (int i = 1; i <= v; i++)
    {
        if (!is_house[i])
            continue;
 
        if (is_mac_or_star[i][0] && is_mac_or_star[i][1]) // 맥세권이면서 스세권이면
            ans = min(ans, dist[i][0] + dist[i][1]); // 그 합이 최소인 경우에 대해서 파악
    }
 
    if (ans == INF) // 조건을 만족하는 집이 없는 경우
        cout << -1 << endl;
 
    else cout << ans << endl;
 
    return 0;
}