[ 백준 5214 ] 환승 (C++)

백준의 환승(5214) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본인은 이 문제를 보자마자, 생각 없이 냅다 BFS탐색을 통해서 정답을 도출해 냈다. 하지만 메모리초과로 Fail을 받게

   되었다. 사실, 구현의 어려움보다는 이 부분에 대한 어려움이 더 심한 문제라고 생각한다.

   메모리초과가 왜 나는지, 어떻게 해결하는 것인 좋은지에 대해서 생각을 해보자.

   먼저 메모리초과가 왜 발생할까 ??? 쉬운 예제를 통해서 최악의 경우를 생각해보자.

   만약에 하이퍼튜브가 정점 3개를 연결한다고 가정해보자. 그럼 이 때 생성되는 간선들을 모두 적어보면 아래와 같다.

   1 - 2 , 1 - 3 , 2 - 3 , 2 - 1 , 2 - 3, 3 - 1, 3 - 2

   즉, 간선이 (K-1)^2 보다는 크고 (K^2)보다는 작은 갯수의 간선이 생성되게 된다.

   이를 빅오 표기법에 의해서 표기해보면 약 K^2의 간선이 생성된다고 볼 수 있다.

   그렇다면 최악의 경우를 생각해보자. 하이퍼튜브가 1000개가 있고, 서로 연결하는 역의 갯수가 1000개가 있다면 ?

   그대로 간선을 다 연결해버리면 몇 개의 간선이 생성될까 ??

   아마, 약 1000 x 1000^2 개 즉, 1000^3개 만큼의 간선이 생성되게 될 것이다.

   1000^3이면 약 10억을 의미하는데, 본인이 대략적으로 알기로 1억칸이 넘어가면 메모리의 300MB정도를 사용하는 것으로

   알고 있다. 즉, 10억개를 저장하려면 문제에서 제한한 256MB를 당연히 초과할 수 밖에 없다.

   이 이유 때문에 있는 간선을 그대로 연결해버리면 메모리초과가 발생하게 된다.

   그렇다면 이 메모리초과를 어떻게 해결해야할까?

   본인은 '하이퍼튜브 또한 하나의 역으로 바라보는 방법' 으로 해결해보았다.

   위에서 문제점이 뭐였는지 다시 한번 생각을 해보자. 역들끼리 연결하게 되면 중복되는 간선이 많아지게 되고

   중복되는 간선들에 의해서 메모리초과가 발생했다. 그렇다면 하이퍼튜브를 하나의 정점 or 역으로 바라보게 되면

   어떻게 될까?? 바로 아래의 그림과 같이 연결이 가능하다.

  

   위의 그림과 같이 연결이 가능하다. 중간에 H.1은 1번 하이퍼튜브를 의미한다. 이런식으로 연결하게 되면 간선의 갯수가

   6개에서 3개로 줄어든 것을 확인할 수가 있다. 즉, 생성되는 간선의 갯수가 서로 연결되어 있는 역의 갯수를

   넘지를 않게 된다. (위의 그림에서 서로 연결되어 있는 역 = 3개 , 간선의 갯수 = 3개)

   그렇다면 이를 토대로 최악의 경우를 계산해보면, 1000개의 하이퍼튜브가 1000개의 역들을 연결한다고 가정해보면

   1000 x 1000 으로 해결이 가능하다. 즉, 메모리를 훨씬 덜 쓰고도 간선들을 연결할 수 있다는 것을 의미한다.

2) 그렇다면 위에서 하이퍼튜브를 역으로 생각하는 방법을 알아보았는데, 그렇다면 여기서 하이퍼튜브를 어떻게 역으로

   계산을 해줘야할까? 바로 'Dummy Node'를 이용해서 해결할 수 있다.

   말 그대로 해석해보자면 '별 의미 없는 노드'이다. 즉, 별 의미 없는 노드가 저장될 공간을 추가적으로 선언해줌으로써

   그 공간에 하이퍼튜브들을 저장하는 것이다.

  

   우리가 일반적으로 풀었다면 아마 역을 저장하는 벡터든 배열이든 크기를 100001로 잡았을 것이다.

   그런데 여기에 + 1000을 해서 101000칸을 생성해주는 것이다. 그럼 저 뒤에 1000칸에는 무엇이 저장될까?

   바로 하이퍼튜브가 하나의 역으로 저장이 되는 것이다.

   즉, 1번부터 100000까지는 실제 역이 저장되는 공간이고, 100001 ~ 101000번은 하이퍼튜브가 저장되는 공간이다.

   선언을 이렇게 더 크게 해놓은 후에, 우리는 입력으로 역의 갯수인 N을 입력받게 된다.

   그럼 우리는 N + 1번부터를 하이퍼튜브가 저장될 공간으로 사용하면 된다.

3) 역의 갯수를 탐색하는 방법으로는 BFS 알고리즘을 이용한 완전탐색 방법을 사용해보았다.

   현재 역과 연결되어 있는 모든 노드들을 탐색하면서, 만약 그 노드가 하이퍼튜브 노드일 경우, 역의 갯수를 Count하지 않았

   고 역과 역을 옮겨가는 경우에는 역의 갯수를 Count해주는 방식으로 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 100000 + 1
using namespace std;
 
int N, K, M;
int Cost[MAX + 1000];
vector<int> Station[MAX + 1000];
 
void Input()
{
    cin >> N >> K >> M;
    for (int i = 1; i <= M; i++)
    {
        for (int j = 0; j < K; j++)
        {
            int a; cin >> a;
            Station[a].push_back(i + N);
            Station[i + N].push_back(a);
        }
    }
}
 
int BFS()
{
    queue<int> Q;
    Q.push(1);
    Cost[1] = 1;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front();
        Q.pop();
 
        if (Cur == N) return Cost[Cur];
 
        for (int i = 0; i < Station[Cur].size(); i++)
        {
            int Next = Station[Cur][i];
            if (Cost[Next] == 0)
            {
                if (Next > N) Cost[Next] = Cost[Cur];
                else Cost[Next] = Cost[Cur] + 1;
                Q.push(Next);
            }
        }
    }
    return -1;
}
 
void Solution()
{
    int Answer = BFS();
    cout << Answer << 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;
}