C++ 백준 5214 환승

백준 5214

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

5214번: 환승

풀이 전 나의 생각

하이퍼튜브의 정보가 주어졌을 때, 1번역에서 N번역으로 갈 수 있는 최소 역의 수를 구해야 한다.

 

조건

- (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

- K는  서로 연결하는 역의 번호

 

과정

처음 문제를 보면 서로 역을 연결하고 있다는 키워드를 볼 수 있다.

그래서 자연스럽게 그래프를 떠올릴 수 있고 어떻게든 주어진 역들의

정보를 저장하려고 한다.

 

예를 들어 (1, 2, 3) 역의 연결 정보가 주어졌을 때

1 = 2, 3 

2 = 1, 3

3 = 1, 2

이런 형식으로 역의 정보를 저장하려고 시도하는데 결국 답을 구해낼 순 있겠지만

문제에서 주어진 메모리 제한 256 MB를 만족시키지 못하며 메모리 초과가 발생할 것이다.

 

주어진 K와 M의 제한은 1000이다.

1. 역 하나에 이어진 역들의 정보를 최대로 넣을 수 있는 횟수는 1000이다.

2. 1의 과정을 K의 최대 범위인 1000개 까지 진행한다. 

3. 1, 2의 과정을 M의 최대 범위인 1000번 반복한다.

 

-> 이때 1000 * 1000 * 1000 = 10억의 공간이 필요한데 256 MB의 최대 바이트는 

256 * 1024 * 1024 = 약 2.6억 바이트, 최대한 양보해서 한 공간을 1 바이트라고 가정해도 10억 바이트를

사용하기 때문에 메모리 초과가 발생한다.

 

그러므로 이를 해결하기 위해 간선의 정보를 최대한 줄여줘야 한다.

 

문제를 보면 하이퍼튜브가 서로 연결하는 역의 개수가 주어진다.

그러므로 하이퍼튜브가 연결하는 역에 집중하는 것이 아닌,

하이퍼튜브를 기준으로 역의 간선 정보를 저장해준다면 

1000 * 1000으로 256 MB안에서 문제를 해결할 수 있다.

 

예를 들어, 1 = 2, 3의 형태로 간선정보를 넣어주는 것이 아닌

첫 번째 하이퍼튜브 = 1, 2, 3의 형태로 정보를 넣어준다.

 

이런 형식 일때, 1이 첫 번째 하이퍼 튜브와 두 번째 하이퍼 튜브의 정보를 갖고 있다면

두 번째 하이퍼 튜브에 연결 되어있는 역들에 접근할 수 있다.

 

과정은 다음과 같다.

1. 하이퍼 튜브라는 더미 노드를 만들어서 연결된 역들의 정보를 저장해준다.

2. BFS로 탐색하며 각 역이 몇 단계를 거쳐 왔는지 저장해준다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int N, K, M;
vector<vector<int>>station(101001);
bool visited[101001];

int bfs(int st)
{
	queue<pair<int, int>> q;
	visited[st] = true;
	q.push(make_pair(st, 1));

	while (!q.empty())
	{
		int now_station = q.front().first;
		int now_step = q.front().second;
		q.pop();

		//N까지 모두 탐색을 완료했다면 문제에서 요구하는 단계값 리턴
		if (now_station == N) return now_step;

		for (int next : station[now_station])
		{
			if (!visited[next])
			{
				//현재 역이 N보다 크다면 하이퍼 튜브 노드
				if (next > N)
				{
					visited[next] = true;
					q.push(make_pair(next, now_step));
				}
				// 하이퍼 튜브 노드가 아니라면 단계 증가
				else
				{
					visited[next] = true;
					q.push(make_pair(next, now_step + 1));
				}
			}
		}
	}

	return -1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> K >> M;

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

			//하이퍼 튜브 더미 노드에 역 정보 저장 
			//(i + N)을 하는 이유는 하이퍼 튜브 노드인지 아닌지 확인하기 위함이다. (현재 역이 N보다 크다면 하이퍼 튜브 노드)
			station[hyper_Info].push_back(i + N);
			station[i + N].push_back(hyper_Info);
		}
	}

	cout << bfs(1);
}