[백준 5214] 환승

초반에 문제를 좀 잘못 이해해서 고치는 데 시간을 좀 썼다. 첨에보고 단순한 인접리스트 + BFS문제인지 알았다.

문제풀이

 

조금 신선한 방식의 문제였다. 하이퍼 튜브내에선 서로서로 바로바로 갈수있다는 개념을 적용하기위해 단순한 graph에서 가상의 node(역)를 추가하여 가상의 역인 경우에는 실제로 횟수를 올리지 않는 방법으로 구현하였다. 

소스코드

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;
 
int N,K,M;
 
vector<int> graph[MAX+1000];
bool visited[MAX+1000];
 
typedef struct Info{
    int station;
    int cnt;
    Info(int s, int c){station =s;cnt=c;}
}Info;
 
int BFS(){
    queue<Info> q;
    q.push(Info(1,1));
    visited[1] = true;
    
    while(!q.empty()){
        Info cur = q.front();
        q.pop();
        if(cur.station==N){
            return cur.cnt;
        }
        for(int i=0;i<graph[cur.station].size();i++){
            int next= graph[cur.station][i];
            if(!visited[next]){
                if(next>N){ //가상역
                    q.push(Info(next,cur.cnt));
                }
                else{
                    visited[next] = true;
                    q.push(Info(next,cur.cnt+1));
                }
               
            }
        }
    }
    return -1;
}
 
int main() {
    cin>>N>>K>>M;
    for(int i=1;i<=M;i++){
        for(int j=0;j<K;j++){
            int a;
            cin>> a;
            graph[a].push_back(i+N);
            graph[i+N].push_back(a);
        }
    }
    
    cout<<BFS()<<endl;
    
    return 0;
}
 

 

 

문제 링크 : https://www.acmicpc.net/problem/5214

5214번: 환승