[알고리즘] 백준 2458번: 키 순서 (C++)

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

2458번: 키 순서

단방향 BFS로 풀 수 있을까도 했지만 코드가 더러워질 거 같아서 플로이드 와샬로 풀었다.

>> 플로이드 와샬은 한 번만 돌려도 모든 노드로부터 모든 노드까지 구할 수 있기 때문이다.

>> BFS나 다익스트라는 한 노드로부터 모든 노드로의 최단 경로를 구하기 때문에 N번(노드 개수) 돌려야 한다.

 

[솔루션]

1) 모든 가중치는 1로 설정한다.

2) 최단 경로가 0이면 자기 자신, INF이면 갈 수 있는 방법이 없다는 뜻

3) 즉, 그 외에는 갈 수 있는 방법이 있다는 뜻이다.

>> 이것은 출발 노드와 도착 노드 간의 키 비교가 가능하다는 뜻이 된다.

4) 최단 경로가 자기 자신을 제외한 N - 1개가 주어지면 모든 노드와 키 비교가 가능하다.

 

int result = 0;
for (int i = 1; i <= n; i++) {
	int cnt = 0;

	// i로부터 갈 수 있는 노드가 몇 개인가
	for (int j = 1; j <= n; j++) {
		if (cache[i][j] == INF || cache[i][j] == 0) continue;
		else cnt++;
	}

	// 도착 노드가 i가 되는 경우는 몇 개인가
	for (int j = 1; j <= n; j++) {
		if (cache[j][i] == INF || cache[i][j] == 0) continue;
		else cnt++;
	}

	if (cnt == n - 1) result++;
}

이 부분이 이번 문제의 핵심이다. 

---

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX 500 + 1
#define INF 987654321
using namespace std;

int graph[MAX][MAX];
int cache[MAX][MAX];
int n, m;

void floydWarshall() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cache[i][j] = graph[i][j];
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (cache[i][k] != INF && cache[k][j] != INF) {
					cache[i][j] = min(cache[i][j], cache[i][k] + cache[k][j]);
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) cache[i][j] = 0;
		}
	}
}

int main() {
	cin >> n >> m;

	// init
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a][b] = 1;
	}

	floydWarshall();

	int result = 0;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;

		// i로부터 갈 수 있는 노드가 몇 개인가
		for (int j = 1; j <= n; j++) {
			if (cache[i][j] == INF || cache[i][j] == 0) continue;
			else cnt++;
		}

		// 도착 노드가 i가 되는 경우는 몇 개인가
		for (int j = 1; j <= n; j++) {
			if (cache[j][i] == INF || cache[i][j] == 0) continue;
			else cnt++;
		}

		if (cnt == n - 1) result++;
	}

	cout << result;

	return 0;
}