백준 2458 c++ "키 순서" -[PlusUltraCode]

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

2458번: 키 순서

 

[필자 사고]

 

대표적인 순서 알고리즘 -> 플로이드 와샬 알고리즘을 써야 되는 문제이다.

 

플로이드 와샬 알고리즘의 개념이 부족하면 문제를 해결하기 쉽지 않았을 것이다.

 

간단하게 설명하자면 플로이드 와샬 알고리즘의 특징은 어떤 경로가 존재한다면 최단거리를 배열에 값에

저장해 놓는 알고리즘이다.

 

이 문제의 특징은 키 순서이다. 플로이드 와샬 알고리즘을 사용하면 1->4로 갈경우는 자연수로 되어 있지만

 

4->1로 갈 경우 무한대 수가 있을 수 있다. 이러한 경우를 방지하기 위해 플로이드 와샬 알고리즘 마지막 부분에

 

1->4부분이 자연수로 되어 있으면 4->1 부분의 값도 자연수로 넣어주었다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N, M;

vector<vector<int>> Arr;

void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	for (int i = 0; i <= N; i++) {

		Arr[i].resize(N + 1,987654321);
	}

	for (int i = 0; i <M; i++) {
		int s, e;
		cin >> s >> e;
		Arr[s][e] = 1;
		
	}
	for (int i = 0; i <= N; i++) {
		Arr[i][i] = 0;
	}
}

void Floyd_Warshall() {
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				Arr[s][e] = min(Arr[s][e], Arr[s][k] + Arr[k][e]);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			if (Arr[i][k] != 0 && Arr[i][k] != 987654321) {
				Arr[k][i] = 1;
			}
		}
	}
}

int main(void) {

	Input();
	Floyd_Warshall();
	int ResultCount = 0;
	for (int i = 1; i <= N; i++) {
		bool check = true;
		for (int k = 1; k <= N; k++) {
			if (Arr[i][k] == 987654321) {
				check = false;
				break;
			}
		}
		if (check == true) {
			ResultCount++;
		
		}
	}
	

	cout << ResultCount;
}