BOJ 5214 - 환승 [C++]

 

문제

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

$N$개의 역과 $M$개의 하이퍼튜브가 존재하며, 하이퍼튜브 하나는 역 $K$개를 서로 연결한다.
$1$번 역에서 $N$번 역으로 가는데 방문하는 최소 역의 수를 구해보자.

풀이

하나의 하이퍼튜브가 연결하는 $K$개의 역을 서로 모두 이어주게 된다면, 간선이 $\dfrac{K(K-1)}{2}$개 생기게 된다.

아래는 2, 4, 5, 7, 8, 9번 역을 연결하는 하이퍼튜브를 그래프에 추가시킨 그림이다.

이 방식대로 그래프를 구성한다면 전체 간선은 $O(MK^2)$만큼 생기게 되고, 이는 메모리나 시간의 제약으로 인해 불가능한 풀이가 된다.

---

하이퍼튜브 하나를 그래프의 새로운 가상의 정점으로 본다면 어떨까?

하나의 하이퍼튜브로 인해 추가되는 간선은 $K$개 뿐이다. 따라서 전체 간선의 개수는 $MK$개로, 최대 $1\,000\,000$개만 추가되는 것을 알 수 있다.

---

$i$번째 하이퍼튜브를 그래프에서 $N+i$번 정점으로 대응시킨다면 전체 정점은 $N+M$개, 간선은 $MK$개인 그래프를 구성할 수 있다.

만들어진 그래프에서 BFS로 최단 거리를 구하면 될 것같이 생겼다.

그러나 하이퍼튜브를 나타내는 가상의 정점을 지날 때 비용이 발생해서는 안 된다.

 

현재 점에서 다른 역을 방문할 때는 비용이 $1$ 발생한다고 볼 수 있지만, 하이퍼튜브를 방문할 때는 비용이 발생하지 않는다.

가중치가 두 종류$(0,1)$ 뿐인 그래프 상에서 최단 경로를 구하는 문제로 바뀐 셈이다.

따라서 0-1 BFS로 해결할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;

int N, K, M;
vector<vector<int>> v(101001);

int bfs01(int start, int end) {
	vector<int> dist(101001, INF);
	deque<pair<int, int>> q;
	dist[start] = 1;
	q.emplace_back(1, start);
	while (!q.empty()) {
		auto [d, n] = q.front(); q.pop_front();
		for (int i : v[n]) {
			int cost = i > N ? 0 : 1;
			if (dist[i] > d + cost) {
				dist[i] = d + cost;
				if (cost) q.emplace_back(dist[i], i);
				else q.emplace_front(dist[i], i);
			}
		}
	}
	return dist[end] == INF ? -1 : dist[end];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> K >> M;
	for (int i = 1; i <= M; i++) {
		for (int j = 1, a; j <= K; j++) {
			cin >> a;
			v[a].push_back(N + i);
			v[N + i].push_back(a);
		}
	}

	cout << bfs01(1, N);

}