[백준/BOJ] 백준 5214번 : 환승

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

5214번: 환승

하이퍼튜브 하나를 노드로 만들고 하이퍼 튜브와 연결된 역(노드)을 연결한다.

 

코드

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

int n, k, m;
vector<int> adj[101001];
int discovered[101001];
int depth[101001];

int Solve(int start, int dest)
{
	memset(discovered, 0, sizeof(discovered));
	discovered[start] = 1;
	depth[start] = 0;

	queue<int> q;
	q.push(start);

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

		//목적지에 도착했을때
		//하이퍼튜브 노드를 거쳐서 가므로 나누기 2를 한것이고, 출발노드(start역)을 포함해서 +1을 한다
		if (here == dest)
			return depth[here] / 2 + 1;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];
			if (discovered[there] == 0)
			{
				discovered[there] = 1;
				depth[there] = depth[here] + 1;

				q.push(there);
			}
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp;

	cin >> n >> k >> m;

	//하이퍼튜브 하나를 노드로 만들고 하이퍼 튜브와 연결된 역(노드)를 연결한다
	for (int i = 1; i <= m; i++)
	{
		for (int j = 0; j < k; j++)
		{
			cin >> temp;
			adj[n + i].push_back(temp);
			adj[temp].push_back(n + i);
		}
	}

	cout << Solve(1, n);

	return 0;
}