[BOJ/Gold 2] 백준 5214 환승(C++)

문제 링크

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을 출력한다.

예제 입력 1

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

예제 출력 1

4

1-3-6-9나 1-5-6-9로 이동하면 된다.

예제 입력 2

15 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 13

예제 출력 2

3

알고리즘 분류

• 그래프 탐색

풀이

하이퍼튜브를 하나의 역으로 생각한다면 매우 쉬워지지만 그 아이디어를 떠올리는 게 어려웠다. 오늘도 하나 배워간다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 101001
#define LL long long
#define INF 2e9

using namespace std;
int N, K, M;
vector<int> Platform[MAX];
bool visited[MAX];

int BFS() {
	queue<pair<int, int> > Q;
	visited[1] = true;
	Q.push(make_pair(1, 1));

	while (!Q.empty()) {
		int CurX = Q.front().first;
		int CurCnt = Q.front().second;
		Q.pop();

		if (CurX == N) {
			return CurCnt;
		}

		for (int i = 0; i < Platform[CurX].size(); i++) {
			int nextX = Platform[CurX][i];
			if (!visited[nextX]) {
				visited[nextX] = true;
				if (nextX > N) {
					Q.push(make_pair(nextX, CurCnt));
				}
				else {
					Q.push(make_pair(nextX, CurCnt + 1));
				}
			}
		}
	};

	return -1;
}

int main() {
	FIRST
	cin >> N >> K >> M;
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < K; j++) {
			int X;
			cin >> X;
			Platform[X].push_back(i + N);
			Platform[i + N].push_back(X);
		}
	}
	cout << BFS() << "\n";

	return 0;
}