[백준] 골드2 : (5214) 환승

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

 

보통 BFS에서는 정점이 하나의 종류이지만, 이 문제에서는 정점을 두 종류로 나누어 푸는 것이 좋다.

"역"에 대한 정점과 "하이퍼튜브"를 정점으로 두고 배열을 저장한다.

이러면 각 입력의 최댓값인 100,000개와 1,000개가 주어져도 101mb를 차지하기 때문에 메모리 초과를 해결할 수 있다.

 

정점들을 저장할 때, 시작 역인 1번 역을 포함하는 하이퍼튜브들을 따로 저장한다.

문제가 1번 역에서 시작하여 마지막 역에 도착하는 것이니, 무조건 1번 역으로 시작해야 하기 때문이다.

 

1번 역이 포함된 하이퍼튜브들을 대상으로 BFS를 수행하여 최단 거리를 구한다.

 

BFS 로직

방문한 하이퍼튜브를 체크하여 순환이 일어나지 않도록 한다.

현재 하이퍼튜브에서 갈 수 있는 역과 현재 역까지 걸리는 거리를 queue로 관리한다.

 

시작 하이퍼튜브에서 갈 수 있는 역을 queue에 담고, 각 역을 순회한다.

현재 역에서 갈 수 있는 하이퍼튜브를 순회하고, 방문하지 않은 하이퍼튜브라면 해당 하이퍼튜브에서 갈 수 있는 역을 queue에 담는 과정을 마지막 역이 나올 때까지 반복한다.

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

pair<int, bool> BFS(vector<vector<int>>& Stations, vector<vector<int>>& HyperTubes, const int SHyperTube, const int N)
{
	// 방문한 하이퍼튜브 체크
	vector<bool> VisitHyperTube(1000, false);
	VisitHyperTube[SHyperTube] = true;

	// 현재 하이퍼튜브에서 갈 수 있는 역을 queue에 담음
	queue<int> q, qn;
	for (const auto& i : HyperTubes[SHyperTube])
	{
		if (i == N) return { N == 1 ? 1 : 2, true };
		q.push(i), qn.push(2);
	}

	while (!q.empty())
	{
		int CurStation = q.front(), n = qn.front();
		q.pop(), qn.pop();

		// 현재 역에서 갈 수 있는 하이퍼튜브를 순회
		for (const auto& i : Stations[CurStation])
		{
			// 방문하지 않은 하이퍼튜브라면, 해당 하이퍼튜브에서 갈 수 있는 역을 queue에 담음
			if (!VisitHyperTube[i])
			{
				VisitHyperTube[i] = true;
				for (const auto& j : HyperTubes[i])
				{
					if (j == N) return { n + 1, true };
					if (!VisitStations[j]) q.push(j), qn.push(n + 1);
				}
			}
		}
	}

	return { 0, false };
}

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

	int N, K, M, Answer = 987654321;
	cin >> N >> K >> M;

	// 각 하이퍼튜브가 갈 수 있는 역
	vector<vector<int>> HyperTubes(M);

	// 각 역마다 탈 수 있는 하이퍼튜브
	vector<vector<int>> Stations(N + 1);

	// 1번 역을 포함하는 하이퍼튜브 (시작 하이퍼튜브)
	vector<int> SHyperTubes;

	for (int i = 0; i < M; ++i)
	{
		for (int j = 0, k; j < K; ++j)
		{
			cin >> k;
			// 현재 하이퍼튜브가 갈 수 있는 역
			HyperTubes[i].push_back(k);

			// 현재 역과 연결되어있는 하이퍼튜브
			Stations[k].push_back(i);

			// 시작 역인 1번 역을 포함하는 하이퍼튜브 저장
			if (k == 1) SHyperTubes.push_back(i);
		}
	}

	// 1번 역을 포함하는 각 하이퍼튜브마다 BFS 수행
	for (const auto& i : SHyperTubes)
	{
		pair<int, bool> Ret = BFS(Stations, HyperTubes, i, N);
		if (Ret.second) Answer = min(Answer, Ret.first);
	}

	if (Answer != 987654321) cout << Answer << "\n";
	else cout << -1 << "\n";
}