BOJ - 5124. 환승 (삼성기출)

문제

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

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다.

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

예제 입력 1

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

예제 출력 1

4

 

---

풀이

인접리스트로 최단거리를 찾는 BFS 탐색 문제 - 그러나, 역과 하이퍼튜브 두 가지가 존재한다.

하이퍼튜브도 하나의 역으로 생각하는 것이 가장 중요하다.

문제에서 역의 개수는 최대 10만개만큼 받을 수 있다고 한다.

그러면 하이퍼튜브를 10만번 이후의 번호에 저장해놓자!

즉, 1번 하이퍼튜브는 100001, 2번 하이퍼튜브는 100002

for(int i=1;i<=m;i++){
        for(int j=0;j<k;j++){
            int a;
            cin>>a;
            //1번역 100001(하이퍼튜브)와 연결
            //100001(하이퍼튜브)는 1번역과 연결
            stationAndHyper[a].push_back(i+100000);
            stationAndHyper[i+100000].push_back(a);
        }
    }

그리고 일반적인 BFS 탐색을 진행해주면된다.

그러나 답을 출력할 때, 고려해줄 부분이 하나 있다.

문제에서는 최소 방문 역의 개수를 요구한다. 그러나, 탐색을 진행하면 역과 하이퍼튜브를 모두 방문해서 카운트한다. 하이퍼튜브는 답을 출력할 때 빼줘야하므로

if(cur==n){
            //n번역 방문하면
            cout<<count/2+1;
            return;
        }

반으로 나누고 +1해주면 문제가 원하는 요구사항을 만족할 수 있다.

---

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;
int n,k,m;
vector<int> stationAndHyper[101002];
bool visit[101002];

void bfs(){
    queue<pair<int,int>> q;
    q.push(make_pair(1,1));//1번역출발, 역의개수:1
    visit[1] = true;

    while(!q.empty()){
        int cur = q.front().first;
        int count = q.front().second;
        q.pop();
        if(cur==n){
            //n번역 방문하면
            cout<<count/2+1;
            return;
        }
        for(int i=0;i<stationAndHyper[cur].size();i++){
            int next = stationAndHyper[cur][i];
            if(visit[next]==true){
                //방문한적이 있으면
                continue;
            }
            q.push(make_pair(next,count+1));
            visit[next]=true;
        }

    }
    cout<<-1;    
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>k>>m;
    for(int i=1;i<=m;i++){
        for(int j=0;j<k;j++){
            int a;
            cin>>a;
            //1번역 100001(하이퍼튜브)와 연결
            //100001(하이퍼튜브)는 1번역과 연결
            stationAndHyper[a].push_back(i+100000);
            stationAndHyper[i+100000].push_back(a);
        }
    }
    bfs();
    return 0;
}