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

백준의 집 구하기(13911) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 처음에 본인은 모든 맥도날드와 스타벅스의 정점에서 너비우선탐색(BFS)으로 각 집까지의 거리를 구한 후,

   최소 거리를 더하는 식으로 구현했지만 시간초과가 발생했다.

   이렇게 계산할 경우, 최악의 경우에 맥도날드의 수 = 9998개 , 스타벅스의 수 = 9998개, 정점의 갯수 = 10000 개로

   9998 x 10000 + 9998 x 10000 이라는 연산을 진행해야 하기 때문에, 제한시간인 1초 내에 패스를 받을 수가 없다.

   그래서 본인은 더미노드를 이용해서 구현해보았다.

   더미노드 라는 것은, 실제로 존재하는 노드는 아니지만, 특정 목적을 가지고(연산 횟수를 줄인다거나, 메모리를 줄인다거나)

   사용하는 노드이다.

   이 문제에서는 본인은 '모든 맥도날드와 거리가 0인 정점' 하나와 '모든 스타벅스와 거리가 0인 정점' 하나를 이용해서

   구현하였다. 그림으로 보자면 다음처럼 진행되는 것이다.

  

    이 상태에서, 맥도날드의 더미노드에서 각 집까지의 거리, 스타벅스 더미노드에서 각 집까지의 거리를 구한다면

    맵을 전체적으로 총 2번(맥도날드 1번, 스타벅스 1번) 만 탐색을 하면 구할 수 있다.

    본인은 벡터에 연결관계를 저장해 주었는데, 맥도날드의 더미노드는 10001번, 스타벅스의 더미노드는 10002번

    인덱스에 저장해 주었다.

    이 후, 모든 거리를 구한 후, 문제의 조건에 맞는 거리를 만족하는 값 중에서 최소값을 찾아주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 10010
#define M_Parent 10001
#define S_Parent 10002
#define INF 987654321
using namespace std;
 
int V, E, M_Num, S_Num, M_limit, S_limit;
int Dist[MAX][2];
bool Store[MAX];
vector<pair<int, int>> Node[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> V >> E;
    for (int i = 1; i <= V; i++)
    {
        Dist[i][0] = INF;
        Dist[i][1] = INF;
    }
 
    for (int i = 0; i < E; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Node[a].push_back(make_pair(b, c));
        Node[b].push_back(make_pair(a, c));
    }
    cin >> M_Num >> M_limit;
    for (int i = 0; i < M_Num; i++)
    {
        int a; cin >> a;
        Node[M_Parent].push_back(make_pair(a, 0));
        Store[a] = true;
    }
    cin >> S_Num >> S_limit;
    for (int i = 0; i < S_Num; i++)
    {
        int a; cin >> a;
        Node[S_Parent].push_back(make_pair(a, 0));
        Store[a] = true;
    }
}
 
void Find_Distance(int N, int Idx)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(N, 0));
    Dist[N][Idx] = 0;
 
    while (Q.empty() == 0)
    {
        int Current = Q.front().first;
        int Distance = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < Node[Current].size(); i++)
        {
            int Next = Node[Current][i].first;
            int NCost = Node[Current][i].second;
 
            if (Distance + NCost < Dist[Next][Idx])
            {
                Dist[Next][Idx] = Distance + NCost;
                Q.push(make_pair(Next, Distance + NCost));
            }
        }
    }
}
 
void Solution()
{
    Find_Distance(M_Parent, 0);
    Find_Distance(S_Parent, 1);
    int Min_Dist = INF;
    for (int i = 1; i <= V; i++)
    {
        if (Store[i] == true) continue;
        if (Dist[i][0] > M_limit || Dist[i][1] > S_limit) continue;
 
        Min_Dist = Min(Min_Dist, Dist[i][0] + Dist[i][1]);
    }
    if (Min_Dist == INF) cout << -1 << endl;
    else cout << Min_Dist << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}