[백준11562] 백양로 브레이크 (C++)

📌 문제

BOJ 바로가기

양방향 통행이 가능한 도로와 일방향 통행만 가능한 도로가 있다. 한 건물에서 다른 건물이 도착하기까지 몇 개의 일방향 통행 도로를 거슬러 가야 하는지 구해야 한다.

🗡 풀이

이것저것 해보느라 많이 헤맸는데 생각보다 답이 간단했던,,,문제다 ㅎㅎ 😂 어렵다 싶으면 쉽게 가는 방법은 없는지 생각해봐야겠다.

📍 map 배열을 i==j인 경우 0, 아닌 경우 INF로 초기화해준다.

📍 통행이 불가능한 일방향 통로라면 거슬러가야 한다. 따라서 map[v][u]=1로 초기화해준다. u, v 순서로 들어오는 값을 배열의 v행 u열에 넣어주는 게 핵심이다. 그 외의 경우에는 통행이 가능하므로 0으로 초기화해준다.

	if (!b) {
		map[v][u] = 1;
		map[u][v] = 0;
	}
	if (b) {
		map[v][u] = 0;
		map[u][v] = 0;
	}

🚩 소스코드

#include <iostream>
using namespace std;
#define INF 987654321;

int map[251][251];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m, t;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			map[i][j] = i == j ? 0 : INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int u, v, b;
		cin >> u >> v >> b;
		if (!b) {
			map[v][u] = 1;
			map[u][v] = 0;
		}
		if (b) {
			map[v][u] = 0;
			map[u][v] = 0;
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (map[i][j] > map[i][k] + map[k][j]) {
					map[i][j] = map[i][k] + map[k][j];
				}
			}
		}
	}
	cin >> t;
	while (t--) {
		int from, go;
		cin >> from >> go;
		cout << map[from][go] << '\n';
	}
	return 0;
}