[ boj : 5214 ] 환승

 

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

5214번: 환승

해설 : 음,,,처음에 이 문제를 봤을땐 못풀어서 오늘 다시 봐보았습니다. 이 문제가 어제 cj tech 코딩테스트 2번으로 나왔더라구요.

 

일단 모든 역을 그래프와 간선으로 표현하기에는 불가능합니다. n이 10만이고 최대 간선은 n(n-1)/2 개이니 메모리가 감당이 되지 않습니다.

 

그런데 굳이 같은 하이퍼튜브에 속하는 정점들을 간선으로 표현해줄 필요가 있을까요??? 어차피 간선으로 표현해 주지 않더라도 같은 더미데이터에 속해 있다는 건 알고 있는 상태이며 중요한건 어떤 '하이퍼튜브'를 거쳐가는지를 도출해 내는 것이니까요.

 

그러면 차라리 '하이퍼튜브'를 정점으로 표현하고 한번 이동해 위치해 있는 하이퍼튜브에 몇번의 역들이 존재하는지만 알 수 있다면 이후에는 그냥 bfs를 통해 답을 구할 수 있습니다.

 

위와같이 구현을 하려면 우린 2개의 그래프가 필요합니다. 

 

-하이퍼튜브에 어떤 역들이 속해있는지?

-각 역들이 어떤 하이퍼튜브에 속해있는지?

 

그러면 아무리 많아봐야 1000개의 하이퍼튜브에 10만개의 정점들이 표현되고, 그 반대도 마찬가지 입니다.

 

이렇게 되겠죠

 

#include<bits/stdc++.h>

using namespace std;

int n, k, m;
bool edge[100010],tube[1010];
vector<int> A[100010], B[1010];

int bfs();

int main()
{	
	cin >> n >> k >> m;

	int x;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < k; j++) {
			cin >> x;
			A[x].push_back(i);
			B[i].push_back(x);
		}
	}
	cout << bfs();	
	return 0;
}
int bfs()
{
	queue<int> q;
	edge[1] = true;
	q.push(1);
	int cnt = 0;
	while (!q.empty())
	{
		int size = q.size();
		for (int i = 0; i < size; i++) {
			int cur = q.front();
			q.pop();

			if (cur == n)return cnt+1;

			for (int t : A[cur]) {
				if (tube[t])continue;
				tube[t] = true;
				for (int u : B[t]) {
					if (edge[u])continue;

					q.push(u);
					edge[u] = true;
				}
			}
		}
		cnt++;
	}
	return -1;
}