취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5214번 문제인 환승이다.
문제는 아래 링크를 확인하자.

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

문제의 답은 각 하이퍼튜브를 노드로, 서로 환승할 수 있는 관계에 있는 하이퍼튜브 사이의 관계를 에지로 모델링한 그래프 위에서 1번 역이 들어있는 하이퍼튜브(들)로부터 N번 역이 들어있는 하이퍼튜브(들)까지의 거리를 BFS를 이용해 계산해낼 수 있다.

각 역을 지나는 하이퍼튜브들의 목록을 담은 벡터와 각 하이퍼튜브에 포함된 역들의 목록을 담은 벡터를 이용해 중복되는 탐색을 최소화하는 방향으로 구현하고 문제를 해결하자.

별해로 각 역들과 각 하이퍼튜브들을 전부 노드로, 역과 하이퍼튜브의 포함관계를 에지로 모델링한 그래프를 이용해도 문제를 해결할 수 있다.

N이 1로 주어지는 코너케이스에 유의하자.

아래는 제출한 소스코드이다.

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

int S, K, T;

vector<int> tube[100001]; // [s]: s번 역이 들어있는 튜브들을 담은 벡터
vector<int> stn[1001]; // [t]: t번 튜브에 들어있는 역들을 담은 벡터
int tubedist[1001];
bool stnvisited[100001];

void bfs() {
	queue<int> que;
	for (auto& t : tube[1]) tubedist[t] = 2, que.push(t);

	while (!que.empty()) {
		int curt = que.front(); que.pop();
		for (auto& s : stn[curt]) {
			if (stnvisited[s]) continue;
			stnvisited[s] = 1;
			for (auto& t : tube[s]) {
				if (tubedist[t]) continue;
				tubedist[t] = tubedist[curt] + 1;
				que.push(t);
			}
		}
	}
}

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

	cin >> S >> K >> T;

	if (S == 1) {
		cout << 1;
		return 0;
	}

	for (int t = 1; t <= T; t++) {
		for (int k = 0; k < K; k++) {
			int s; cin >> s;
			stn[t].emplace_back(s);
			tube[s].emplace_back(t);
		}
	}

	bfs();

	int ans = 1000000007;
	for (auto& t : tube[S]) {
		ans = min(ans, tubedist[t]);
	}

	if (0 < ans && ans < 1000000007) cout << ans;
	else cout << -1;
}