취미로 코딩하기

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

이번에 볼 문제는 백준 16166번 문제인 서울의 지하철이다.
문제는 아래 링크를 확인하자.

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

BFS를 이용해 문제를 해결하자.

아래와 같이 각 노선이 포함하고 있는 역을 저장하는 벡터와 각 역을 지나는 노선을 저장하는 벡터를 이용하면 구현을 편리하게 할 수 있다.

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

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;

int N;
int idx = 1;
map<ll, int> mp; // {x,i}: x번 역의 새 번호 i
vector<int> L[11]; // [n]: n호선이 포함하는 역 i들
vector<int> S[101]; // [i]: i번 역을 지나는 노선 n들

int dist[101];

void bfs() {
	dist[0] = 1;
	queue<int> que;
	que.push(0);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& n : S[cur]) {
			for (auto& i : L[n]) {
				if (dist[i]) continue;
				dist[i] = dist[cur] + 1;
				que.push(i);
			}
		}
	}
}

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

	mp.insert({0,0});
	cin >> N;
	for (int n = 1; n <= N; n++) {
		int K; cin >> K;
		while (K--) {
			int x; cin >> x;
			if (!mp.count(x)) mp.insert({ x,idx++ });
			x = mp[x];
			L[n].emplace_back(x);
			S[x].emplace_back(n);
		}
	}

	bfs();

	int G; cin >> G;
	if (!mp.count(G)) {
		cout << -1;
		return 0;
	}
	G = mp[G];

	if (G == 0) cout << 0;
	else if (!dist[G]) cout << -1;
	else cout << dist[G] - 2;
}