BOJ : 5214 환승

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

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 4번

이 문제는 입력만 잘 받으면 BFS로 해도 시간초과가 나지 않는다.

핵심은 임의의 열의 개수를 어떻게 vector에 push하느냐 이다.

문제 테스트 케이스를 돌려보면

1 : 10 11 

2 : 10 

3 : 10 12 

4 : 11 

5 : 11 13 

6 : 12 13 14 

7 : 12 13 

8 : 14 

9 : 14 

10 : 1 2 3 

11 : 1 4 5 

12 : 3 6 7 

13 : 5 6 7 

14 : 6 8 9 

가 나온다. 잘 활용해서 풀어보도록 하자.

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
int N,K,M,cnt=1;
vector<int> v[200002];
bool visited[100002];
queue<int> q;
int main(){
    scanf("%d%d%d",&N,&K,&M);
    
    for(int i=0, temp ;i<M;i++){
        for(int j=0;j<K;j++){
            scanf("%d",&temp);
            v[N+i+1].push_back(temp);
            v[temp].push_back(N+i+1);
        }
    }
    q.push(1);
    visited[1]=1;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            int n=q.front();
            q.pop();
            
            if(n==N){
                printf("%d\n",cnt);
                return 0;
            }
            for(auto &l : v[n]){
                for(auto &ln : v[l]){
                    if(visited[ln]) continue;
                    q.push(ln);
                    visited[ln]=1;
                }
            }
        }
        cnt++;
    }
    printf("-1\n");