백준 11562 c++ "백양로 브레이크" -[PlusUltraCode]

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

11562번: 백양로 브레이크

[필자 사고]

이 문제는 플로이드 와샬을 이용하면 쉽게 풀 수 있는 문제라고 생각했다.

 

이런 유형의 문제를 처음 접했다. 

 

이 문제의 특징은 단방향 간선일 경우 Arr배열에 어떠한 값을 넣고 플로이드 와샬 알고리즘을 진행힐자기 관건인 문제이다.

 

곰곰히 생각하고 자료도 찾아보고 깨달은 점은 문제에서 요구하는 단방향 간선을 양방향 간선으로 바꾼다는 말은 즉 반댓 방향으로 갈려면 비용이 1증가한다와 같은 말인 것이다.

 

따라서 초기 배열값들을 무한대로 저장해 놓고 정상적인 방향 값에는 0을 넣었고 역방향에는 1의 비용이 들기 때문에 1을 저장했다.

 

이 배열로 플로이드와샬 알고리즘을 실행하면 원하는 값들을 쉽게 구할 수 있다.

 

[소스 코드]

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

int INF= 987654321;

vector<vector<int>> Arr;
int N, M;
void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		Arr[i].resize(N + 1, INF);
	}
	for (int i = 0; i < M; i++) {
		int s, e, b;
		cin >> s >> e >> b;
		if (b == 0) {
			Arr[s][e] = 0;
			Arr[e][s] = 1;
		}
		else {
			Arr[s][e] = 0;
			Arr[e][s] = 0;
		}
	}
}
void Print() {
	for (int s = 1; s <= N; s++) {
		for (int e = 1; e <= N; e++) {
			cout << Arr[s][e] << " ";
		}
		cout << '\n';
	}
}

void Floyd_Warshall() {

	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				if (s == e)Arr[s][e] = 0;
				if (Arr[s][e] > Arr[s][k] + Arr[k][e]) {
					Arr[s][e] = Arr[s][k] + Arr[k][e];
				}
			}
		}
	}

}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Floyd_Warshall();
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int s, e;
		cin >> s >> e;
		cout << Arr[s][e] << '\n';
	}
}