백준 5214번 환승

겉보기에는 간단한 BFS 문제처럼 보이지만 메모리 제한이 128MB인 것이 함정인 문제였습니다.

우선, 아래는 메모리 초과가 발생한 코드입니다.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

const int MAX = 100000 + 1;

 

int N, K, M;

vector<int> station[MAX];

int hyperTube[1000 + 1];

int cache[MAX]; //해당 인덱스에 도달하는데 지나친 역 수

 

void initialize(void)

{

        //min(cache[next], cache[here]+1)을 위해 INF로 초기화

        for (int i = 0; i < 1001; i++)

                 cache[i] = INF;

}

 

int BFS(void)

{

        queue<int> q;

        q.push(1);

        cache[1] = 1; //1이 시작점이므로

 

        while (!q.empty())

        {

                 int here = q.front();

                 q.pop();

 

                 if (here == N) //목적지에 도달하면 캐시 반환

                         return cache[here];

 

                 //해당역과 연결된 하이퍼튜브 다 가본다

                 for (int i = 0; i < station[here].size(); i++)

                 {

                         int next = station[here][i];

                         //큐에 넣고

                         q.push(next);

                         //지나간 역의 개수 중 최소를 캐시에 저장

                         cache[next] = min(cache[next], cache[here] + 1);

                 }

        }

        return -1; //갈 수 없다

}

 

int main(void)

{

        cin >> N >> K >> M;

       

        for (int i = 0; i < M; i++)

        {

                 for (int j = 0; j < K; j++)

                         cin >> hyperTube[j];

                

                 for (int j = 0; j < K; j++)

                         for (int k = 0; k < K; k++)

                         {

                                 if (j == k)

                                          continue;

                                 else

                                          station[hyperTube[j]].push_back(hyperTube[k]);

                         }

        }

 

        initialize();

 

        cout << BFS() << endl;

        return 0;

}

위 코드가 메모리 초과가 발생하는 이유는 각각의 하이퍼튜브가 1000개씩 연결되어있다면 1000^3이기 때문입니다.

따라서, 메모리 문제를 해결하기 위해서는 graph 벡터 배열에서 dummy station을 이용해야 합니다,

설명을 하자면 N은 100,000까지이므로 100,001부터 가상 역을 만들어 하이퍼튜브를 저장하는 것입니다.

이렇게 한다면 메모리 제한 내 프로그램이 실행되기 때문에 AC를 받을 수 있습니다!

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

const int MAX = 100000 + 1;

 

int N, K, M;

vector<int> station[MAX + 2000];

int cache[MAX + 2000]; //해당 인덱스에 도달하는데 지나친 역 수

 

int BFS(void)

{

        queue<int> q;

        q.push(1);

        cache[1] = 1; //출발역도 지나간 역으로 포함

 

        while (!q.empty())

        {

                 int here = q.front();

                 q.pop();

 

                 if (here == N) //목적지에 도달하면 캐시 반환

                         return cache[here];

 

                 //해당역과 연결된 하이퍼튜브 다 가본다

                 for (int i = 0; i < station[here].size(); i++)

                 {

                         int next = station[here][i];

                         if (cache[next] == 0)

                         {

                                 q.push(next);

                                 //dummyNode라면 실제 역이 아니므로

                                 if (next > MAX)

                                          cache[next] = cache[here];

                                 //실제 역이라면 지나간 역 + 1

                                 else

                                          cache[next] = cache[here] + 1;

                         }

                 }

        }

        return -1; //갈 수 없다

}

 

int main(void)

{

        cin >> N >> K >> M;

       

        for (int i = 1; i <= M; i++)

        {

                 for (int j = 0; j < K; j++)

                 {

                         int node;

                         cin >> node;

                         //dummyNode 이용해서 hypertube 표현(메모리 초과 방지)

                         station[MAX + i].push_back(node);

                         station[node].push_back(MAX + i);

                 }

        }

 

        cout << BFS() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~