[백준 BOJ/C++] 5214 환승

 

5214번: 환승

 

단순한 최단거리 탐색 문제로 보이지만 의외로 정답비율이 낮은편이고 헷갈릴 수 있는 부분이 있는 문제다.
하이퍼튜브라는 컨셉을 문제에서 의도한대로 머릿속에 그리는데 어려움이 있었다.

 

 

문제 설명은 아주 짧고 간단하다.

K개의 역이 주어지고 이 중 1번역에서 N번역까지 도달하는 최단경로를 찾아주면 된다.

간선에는 가중치도 없기 때문에 그냥 보기에는 상당히 간단해 보였다.

 

 

하지만 금방 하이퍼튜브라는 컨셉을 정확히 이해하지 못했음을 깨달았다.

주어지는 경로상 존재하는 역들을 모두 각각 연결하고 하이퍼튜브로 연결된 경로에 대한 비용은 1로 계산 하는 형태로 이해하고 풀었었는데 메모리 제한에 걸리는 상황이 발생했다.

문제의 설명도 너무 짧아 더욱 이해하기 어려웠다.

 

 

 

---

 

 

문제의 포인트

하이퍼튜브 컨셉 이해하기
그래프 표현하기

 

 

하이퍼튜브 컨셉 이해하기

 

하이퍼튜브를 통하면 한번에 이동할 수 있기 때문에 처음엔 각 경로에 주어지는 모든 노드들을 서로 양방향으로 연결시키는 방식으로 접근했다.

예를 들어 "1 2 3" 이라는 경로가 주어지면 1과 2, 1과 3, 2와 3으로 각각 양방향으로 연결을 시켰다.

 

 

이렇게 표현하니 인접 리스트로 구현해도 너무 많은 간선이 만들어졌다.

역의 수가 최대 100,000개이기 때문에 인접 배열로 표현은 애초에 허용될만한 크기가 아니다.

인접 리스트로 표현해도 하이퍼튜브가 연결하는 역의 수가 커질수록 간선 갯수가 많아져 메모리 초과를 피할 수 없었다.

 

 

하이퍼튜브를 어떻게 이해해야 할지 고민 했지만 결과적으로 스스로 그려내진 못했고 다른 분들의 그림을 통해 이해할 수 있었다.

그리고 그림으로 이해하고 최단경로 탐색을 시도했더니 그 이후로는 큰 어려움 없이 문제를 풀어낼 수 있었다.

 

 

 

 

위 그림처럼 하이퍼튜브도 그 자체를 노드로 간주하여 그래프 내에 포함시켜야 한다.

하지만 이렇게 하이퍼튜브를 노드로 그래프에 추가하면 인접 리스트로 그래프를 코드화하는데 있어 불편함이 생긴다.

 

 

그래프 표현하기

 

하이퍼튜브를 노드로 인접 리스트에 추가하기 위해서는 조금 애매한 부분이 생긴다.

각 노드는 순서대로 붙여진 번호로 식별하게 되고 따라서 이 번호가 index가 되어야 하고 또 리스트에 추가될 각 요소로도 사용되어야 한다.

 

 

각 노드들 끼리는 직접 연결되지 않고 하이퍼튜브를 통해서만 연결되기 때문에 예를 들어 "1 2 3" 과 같은 입력이 주어진다면 다음과 같이 인접리스트를 구성하게 된다.

 

 

H1을 인접리스트의 index와 리스트의 노드로도 활용하면서 탐색을 위한 queue에도 편하게 push, pop 할 수 있게 표현할 방법이 필요하다.

하이퍼튜브만의 별도의 리스트를 만드는 등 다양한 방법이 있겠지만 아래와 같이 역의 수인 N 이후의 값을 할당하면 비교적 쉽게 모델링할 수 있었다.

 

N이 9라고 할 때 하이퍼튜브에 N+1인 10부터 순차적으로 번호를 할당하면 N+M 크기의 인접리스트를 이용해 쉽게 이 문제의 그래프를 표현할 수 있다.

 

 

이제는 일반적인 BFS를 이용한 최단경로 탐색만 남았다.

하이퍼튜브를 노드로 추가했기 때문에 경로를 count할 때 N보다 큰 노드를 방문하는지만 확인해서 count를 증가시킬지 판단해주기만 하면 BFS는 간단히 해결된다.

 

---

 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, K, M;

vector<int> adj[100000 + 1000 + 1];
int visit[100000 + 1000 + 1];

void BFS() {
	queue<int> q;

	q.push(1);
	visit[1] = 1;

	while (!q.empty()) {
		int curr = q.front();
		q.pop();

		if (curr == N)
			return;

		for (int i = 0; i < adj[curr].size(); i++) {
			int next = adj[curr][i];

			if (visit[next] <= 0) {
				if (next > N)
					visit[next] = visit[curr];
				else
					visit[next] = visit[curr] + 1;

				q.push(next);
			}
		}
	}
}

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

	int i, j, temp;

	cin >> N >> K >> M;

	visit[N] = -1;
	for (i = 1; i <= M; i++) {
		for (j = 0; j < K; j++) {
			cin >> temp;
			adj[N+i].push_back(temp);
			adj[temp].push_back(N + i);
		}
	}

	BFS();
	cout << visit[N] << "\n";

	return 0;
}