백준 5214번 - 환승

 

5214번: 환승

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

 

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

int N, K, M;

int bfs(vector<vector<int>> graph) {
	vector<int> dis(N + M + 1, 0);
	queue<int> Q;

	Q.push(1);
	dis[1] = 1;

	while (!Q.empty()) {
		int key = Q.front();
		Q.pop();

		for (auto i = graph[key].begin(); i != graph[key].end(); i++) {
			if (dis[(*i)])	continue;
			if (*i > N)	dis[*i] = dis[key];
			else		dis[*i] = dis[key] + 1;
			if (*i == N)	break;
			Q.push(*i);
		}
	}
	if (dis[N] == 0) {
		return -1;
	}
	return dis[N];
}

int main() {
	
	cin >> N >> K >> M;
	vector<vector<int>> graph(N + M + 1);
	int Hsta = 1;
	int sta;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < K; j++) {
			cin >> sta;
			graph[N + Hsta].push_back(sta);
			graph[sta].push_back(N + Hsta);
		}

		Hsta++;
	}
	
	cout << bfs(graph);
}

처음 볼때 은근 쉬워보였는데 입력받으려고 하다보니 딱봐도 메모리초과 뜰 것 같아서 고민했지만 직접 답을 떠올리진 못했다...

 

공간복잡도를 잘 생각해야하는 문제였다. 하이퍼튜브와 하이퍼튜브가 연결하는 역의 수가 모두 최대인 1000이라면  1000^3인 약 1,000,000,000이므로 메모리초과가 발생한다.

따라서 간선의 개수를 줄여주기 위해 하이퍼튜브자체를 하나의 역으로 보고 사용해주어야 한다.

하이퍼튜브가 연결하는 역의 수 K, 하이퍼튜브 수 M으로 수식을 세워보면

원래대로 모든 역에 간선을 연결하면 ((K-1) * K)*M이고, 이를 빅오표기법으로 나타내면 공간복잡도는 O(N^3)

하이퍼튜브를 역으로 보고 연결해주면 2K * M이고, 이를 빅오표기법으로 나타내면 공간복잡도는 O(N^2)가 된다.

1. 위의 방식으로 입력을 받는다. 하이퍼튜브도 역으로 보기로 했으니 그래프의 노드를 총 N+M개 만들어야한다.

2. bfs를 이용해 dis벡터에 1번 역으로 부터의 거리를 표시하면서 N번역까지 간다. 하이퍼튜브는 역으로 보기로 했으나 실제 역은 아니므로 dis값을 1늘리면 안된다.

3. N번역을 만나면 bfs를 종료한다. N역의 dis값이 0이면 -1을 반환하고 아니면 dis[N]값을 반환한다.