백준 5214 - 환승, C++, BFS

5214번: 환승

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, k, m;
int station_count[101001];
vector<int> station[101001];


int Search_Station_Count(){
    queue<int> q;
    q.push(1);
    station_count[1] = 1;

    while(!q.empty()){
        int cur_station = q.front();
        q.pop();

        if(cur_station == n)
            return station_count[cur_station];

        for(int i = 0; i < station[cur_station].size(); i++){
            int next_station = station[cur_station][i];

            if(!station_count[next_station]){
                // Don't count hypertube
                if(next_station > n)
                    station_count[next_station] = station_count[cur_station];
                else 
                    station_count[next_station] = station_count[cur_station] + 1;
                q.push(next_station);
            }
        }
    }
    return -1;
}


int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0);
    cout.tie(0);

    // input
    cin >> n >> k >> m; // station count, hypertube's station, count of hypertube
    for(int i = 1; i <= m; i++){
        for(int j = 0; j < k; j++){
            // station which connected by hypertube
            int input_station;
            cin >> input_station;

            station[i+100000].push_back(input_station);
            station[input_station].push_back(i+100000);
        }
    }

    // solve
    cout << Search_Station_Count() << '\n';
}

---

 하이퍼 튜브를 따로 배열로 선언해 관리하지 않고 기존 역 배열에서 100000을 더해서 i 번 하이퍼튜브를 i +100000 번 역이라고 생각하고 문제를 풀이했습니다. 다른 방법이 있을지는 모르겠지만 찾아보니 이 방식으로 가장 많이 사용하는 것 같습니다.

 

 입력에서 하이퍼튜브와 역을 양방향으로 넣어준 뒤 BFS 과정에서 역의 번호가 n 보다 크면 하이퍼튜브가 되는 것이니 이를 이용해서 역과 하이퍼튜브의 처리를 다르게 해주면 문제를 풀 수 있습니다.