[C/C++] 백준 - 5214번 : 환승 (간선 개수에 의한 메모리 초과)

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

5214번: 환승

문제

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

입력

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

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

출력

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

---

문제만 읽고 단순히 역을 정점, 하이퍼튜브로 간선을 추가하여 역을 연결시켜주는 방법으로 문제를 해결하려했다. 

하지만 그렇게 하게 되면 메모리 초과가 발생한다. 이유는 최대 K개(=1000)의 역을 연결하는 하이퍼튜브가 최대 개수(=1000)가 존재하게 된다면 모든 간선을 양방향으로 연결할 때 메모리 초과가 발생한다.

 

그러면 어떻게 해야할까?

 

각각의 하이퍼튜브가 어떤 역을 연결시켜주는지 저장하고, 각 역에는 어떤 하이퍼튜브가 연결되어있는지 따로 저장해주는 것이다.

모든 역에 간선을 연결하는 방식이 아닌 어떤 하이퍼튜브가 연결되어있는지 저장하고 그 하이퍼튜브에 어떤 역으로 넘어갈 수 있는지 확인하는 방법이다.

 

※ 너비 우선 탐색로 문제를 해결해야 하는 경우 메모리 초과가 발생한다면, 간선 개수에 의해 메모리 초과가 발생할 가능성이 크다. 그럴 경우 정점과 간선을 모두 연결하는 방식이 아닌 정점과 간선을 연결 지어주는 매개체를 따로 저장하여 극복하는 방법으로 구현해야한다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 123456789
#define endl '\n'

using namespace std;

typedef long long ll;
int N, K, M;
vector<vector<int>> hypertube;
vector<vector<int>> station;

void input(){
	cin >> N >> K >> M;
	station.resize(N + 1); 
	hypertube.resize(M + 1);

	for(int i=1;i<=M;i++){
		for(int j=0;j<K;j++){
			int node;
			cin >> node;

			hypertube[i].push_back(node);
			station[node].push_back(i);
		}
	}
}

int solution(){
	vector<int> visited(N + 1, -1);
	vector<int> visitedTube(M + 1, -1);
	queue<pair<int, int>> q;
	q.push({1, 1});
	visited[1] = 1;
	
	while(!q.empty()){
		int node = q.front().first;
		int dist = q.front().second;
		q.pop();

		if(node == N) return dist;

		for(int next=0;next<station[node].size();next++){
			int nextTube = station[node][next];
			if(visitedTube[nextTube] == -1){
				visitedTube[nextTube] = 1;
				for(int station=0;station<hypertube[nextTube].size();station++){
					int nextStation = hypertube[nextTube][station];
					if(visited[nextStation] == -1){
						visited[nextStation] = visited[node] + 1;
						q.push({nextStation, visited[nextStation]});
					}
				}
			}
		}
	}
	return -1;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}