[BOJ] 백준 5214 환승

문제 링크

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

역들을 연결하는 하이퍼튜브가 있고, 각 하이퍼튜브가 서로 연결하는 역들이 주어질 때 1번 역에서 N번 역으로 가는데 방문하는 역의 개수의 최소값을 구해야 한다.

누가 봐도 BFS문제이지만 일반적인 방법처럼 연결된 역들을 모두 그래프로 이어버리면 메모리 초과를 받게 된다.

일반적인 방법대로 풀어보자.

하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M의 범위는 $1 \leq K, M \leq 1,000$이다. 하이퍼튜브 하나당 정점끼리 $K^2$개의 간선이 연결되므로 그래프의 총 간선의 개수는 최악의 경우 $O(MK^2) = 1,000,000,000$개이다. 메모리가 터질 수밖에 없다. 중복된 간선을 여러번 연결했기 때문이다.

 

문제를 해결하기 위해 하이퍼튜브 또한 하나의 정점으로 보고 그래프를 구성하면 된다. 그러면 한 정점에 연결된 간선은 많아야 1000개를 넘지 않게 된다.

하이퍼 튜브를 순서대로 $h_1, ..., h_n$이라 하면 문제의 예제 입력으로부터 다음과 같은 그래프가 그려진다.

역은 항상 하이퍼튜브와, 하이퍼 튜브는 항상 역과 연결된 이분 그래프이다. 

$dist$를 시작점에서부터 현재 노드까지 오는데 건너온 최소의 간선 수라고 정의하자. 1번 역부터 BFS를 돌리면 $dist[n]$을 구할 수 있는데, 항상 튜브 - 역 - 튜브 - 역 의 방식으로 탐색하고, 우리는 방문한 역의 개수를 구해야 하므로 답은 $\frac{dist[n]}{2} + 1$이 된다. 여기서 1을 더해준 이유는 $dist$가 지나온 간선의 수를 저장하기 때문에 시작점인 1번 역이 포함되지 않았기 때문이다.

코드 구현시 $1 \sim n$번 정점을 역으로, $(n+1) \sim (n + m)$번 정점을 하이퍼튜브로 생각하면 쉽게 구현할 수 있다. $n$번 역으로 갈 수 없는 상황처리를 잊지 않도록 주의하자.

정답 코드

	#include <iostream>
	#include <vector>
	#include <queue>
	using namespace std;
	int n, k, m;
	vector<vector<int>> p;
	bool check[110000];
	int dist[110000];
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k >> m;
	p.resize(n + m + 1);
	for (int i = n + 1; i < m + n + 1; i++) {
	for (int j = 0; j < k; j++) {
	int x;
	cin >> x;
	p[i].push_back(x);
	p[x].push_back(i);
	}
	}
	queue<int> q;
	q.push(1);
	check[1] = true;
	while (!q.empty()) {
	int now = q.front();
	q.pop();
	if (now == n) break;
	for (int next : p[now]) {
	if (!check[next]) {
	check[next] = true;
	dist[next] = dist[now] + 1;
	q.push(next);
	}
	}
	}
	if (n != 1 && dist[n] == 0) cout << -1;
	else cout << dist[n] / 2 + 1;
	}

view raw 5214.cpp hosted with ❤ by GitHub