[백준] 5214 - 환승

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

5214번: 환승

 

발상의 전환이 필요했던 문제이다. 나는 발상의 전환을 하지 못해서 다른 분의 블로그를 참고했다.

 

내가 해결하려했던 방법은 입력으로 주어지는 모든 정점 간의 쌍들을 저장하는 것이었다.

하지만 1000 ^ 3의 시간, 공간 복잡도로 통과할 수 없었다.

 

핵심은 하이퍼튜브 노드를 추가하는 것이다.

링크의 예제 입력 1에서 주어지는 입력으로 설명하면,

1 - 2 - 3 을 연결하는 하이퍼튜브 10

1 - 4 - 5 을 연결하는 하이퍼튜브 11

3 - 6 - 7 을 연결하는 하이퍼튜브 12

5 - 6 - 7 을 연결하는 하이퍼튜브 13

6 - 8 - 9 을 연결하는 하이퍼튜브 14

 

이 노드들을 추가하면 간선의 가중치가 0이 되고, 일반적인 bfs로 해결할 수 있다.

 

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

int n, k, m;
vector<vector<int>> v;
int visit[110001];

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k >> m;
	v.resize(n + 10000);

	int t = n + 2;
    
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < k; j++) {
			int num; cin >> num;
			v[num].push_back(t);
			v[t].push_back(num);
		}
		t++;
	}

	queue<int> q;
	q.push(1);
	visit[1] = 1;

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

		for (auto& i : v[a]) {
			if (!visit[i]) {
				if (i > n)visit[i] = visit[a];
				else visit[i] = visit[a] + 1;
				q.push(i);
			}
		}
	}

	if (visit[n])cout << visit[n];
	else cout << -1;
}

 

Reference

https://yabmoons.tistory.com/260