[BOJ 13213 // C++] Binary Roads

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

 

이번에 볼 문제는 백준 13213번 문제인 Binary Roads이다.
문제는 아래 링크를 확인하자.

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

13213번: Binary Roads

문제의 주어진 그래프는 {노드번호, 다음으로 사용할 수 있는 에지의 값}을 노드로 갖는 가중치 없는 방향그래프로 새로이 모델링할 수 있다. 이와 같은 모델링 위에서 주어진 문제는 {0,0}, {0,1}을 시작점으로 할 때 {N-1,0} 또는 {N-1,1}까지의 최단거리를 찾는 문제가 된다.

 

이와 같은 형태의 문제는 bfs를 이용하여 해결 가능하다.

 

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

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

int N, E;
vector<int> G[200000][2];
int dist[200000][2];

void bfs() {
	dist[0][0] = dist[0][1] = 1;
	queue<pair<int, int>> que;
	que.push(make_pair(0, 0));
	que.push(make_pair(0, 1));
	while (!que.empty()) {
		int x = que.front().first, w = que.front().second; que.pop();
		for (auto& nxt : G[x][w]) {
			if (dist[nxt][w ^ 1]) continue;
			dist[nxt][w ^ 1] = dist[x][w] + 1;
			que.push(make_pair(nxt, w ^ 1));
		}
	}
}

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

	cin >> N >> E;
	while (E--) {
		int x, y, w; cin >> x >> y >> w;
		G[x][w].emplace_back(y);
		G[y][w].emplace_back(x);
	}

	bfs();

	int& ans1 = dist[N - 1][0], & ans2 = dist[N - 1][1];
	if (ans1 && ans2) cout << min(ans1, ans2) - 1;
	else if (ans1) cout << ans1 - 1;
	else if (ans2) cout << ans2 - 1;
	else cout << -1;
}