[Beakjoon] 5214 환승 (C++)

문제 링크

BOJ 5214 : 환승

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

풀이

하이퍼튜브라는 개념이 등장하지만, 사실상 간선이 엄청나게 많은 그래프와 같다고 생각했다.

모든 지점에 대해서 간선을 이어준 그래프를 이용해 BFS를 수행하였는데, 메모리 초과가 발생했다.

• 각 하이퍼튜브의 최대 역 연결 개수는 1000개이고 서로 이어준다면 1000^2개.

• 하이퍼튜브의 최대 개수는 1000개이므로 총 1000^3개의 간선정보를 저장해야하기 때문이다.

하이퍼튜브라는 개념을 활용해야겠다고 생각하여 실제로 하이퍼튜브로 가정한 배열을 이용했다.
각 튜브마다 번호를 지정하여 구분하고, 튜브에 속한 역들에 대한 정보를 저장하였다.

map<int, vector<int>> Tube; 

그리고 실제 그래프에는 각 역에 연결돼있는 튜브의 번호를 저장하였다.

하이퍼튜브 한 개가 연결할 수 있는 최대 역의 개수 1000개
하이퍼튜브 최대 개수 1000개이므로 최대 1000^2 메모리 공간을 사용하기 때문에 메모리 사용 측면에서 훨씬 효율적이다

이렇게 튜브 구조를 이용해 그래프를 구성하고, 각 역에 방문할 때마다 해당 역과 연결된 튜브를 순회하면서 다음 방문역을 결정하는 방식으로 BFS를 진행한 다.

튜브 방문 체크

일반적인 BFS는 각 노드에 대한 방문여부를 확인하고 업데이트 한다.
하지만 이 경우는 튜브에 대한 방문여부도 체크해줘야한다.
만약 특정 튜브를 순회한 적이 있다면 가장 처음 방문했을 때 해당 튜브와 연결된 역들에 대한 거리 정보가 최적화돼어 업데이트 된다.
따라서 순회한 적이 있는 튜브는 체크하고 다시 방문하지 않도록 해야 시간초과가 발생하지 않는다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>

#define endl "\n"

using namespace std;

int N, K, M;    
int dist[101010];
bool visitedTube[1010];
map<int, vector<int>> G;
map<int, vector<int>> Tube; 

void Solve() {
    cin>>N>>K>>M;
    
    int n, now, next, a, b, tubeNum;
    vector<int> V;
    queue<int> Q;
    fill(dist,dist+N+1, -1);
    fill(visitedTube, visitedTube+M+1, false);
    
    for(int i=0; i<M; i++){
        V.clear();
        for(int j=0; j<K; j++){
            cin>>n;
            G[n].push_back(i);
            V.push_back(n);
        }
        Tube[i] = V;
    }


    Q.push(1); dist[1] = 1;
    while(!Q.empty()){
        now = Q.front(); Q.pop();
        if(now==N) break;

        for(int i=0; i<G[now].size(); i++){
            
            tubeNum = G[now][i];
            if(visitedTube[tubeNum]) continue;
            visitedTube[tubeNum] = true;
            
            for(int j=0; j<Tube[tubeNum].size(); j++){
                next = Tube[tubeNum][j];
                if(dist[next]>0) continue;
                dist[next] = dist[now]+1;
                Q.push(next);
            }
        }
    }
    cout<<dist[N];
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}