5214번 환승

하이퍼튜브를 하나의 '역'으로 생각하자. ( 예 : 100,001 ~ 100,1001)

DFS로 풀려다가, 생각해보니 안 풀리는 문제여서 BFS로 풀었다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
vector<int> v[102002];
 
int N = 0, K = 0, M = 0;
 
int result = 0;
 
int BFS(int start)
{
    queue<int> q;
 
    bool visit[102002] = { false, };
 
    q.push(start);
 
    visit[start] = true;
 
    int ret = 1; // 1번 역도 포함이다.
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int here = q.front();
 
            q.pop();
 
            if (here == N)
            {
                return ret;
            }
 
            for (auto next : v[here])
            {
                if (!visit[next])
                {
                    visit[next] = true;
                    q.push(next);
                }
            }
        }
 
        ++ret;
    }
 
    return -1; // 도달 실패
}
 
int main(void)
{
    int cnt = 1, vertex = 0;
 
    scanf("%d %d %d", &N, &K, &M);
 
    while (M--)
    {
        for (int i = 0; i < K; i++)
        {
            scanf("%d", &vertex);
 
            v[N + cnt].push_back(vertex);
            v[vertex].push_back(N + cnt);
        }
 
        ++cnt;
    }
 
    int result = BFS(1);
 
    if (result != -1) printf("%d\n", (result + 1) / 2);
    else printf("-1\n");
 
    return 0;
}