C++ [BOJ] 백준 2458번 키 순서 (플로이드 와샬 알고리즘)

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

2458번: 키 순서

---

SOLUTION

플로이드 와샬 알고리즘 문제.

arr배열을 INF로 초기화 하고, 초기 입력을 받아 해당하는 배열 위치의 값을 1로 바꾼다.

입력을 받은 후 플로이드 와샬 알고리즘으로 추가로 비교가 가능한 학생이 있는지 찾아 1로 바꿔준다.

 

arr[i][j], arr[j][i]가 모두 0인 경우에는 키 비교가 불가능 하기 때문에 답에서 제외된다.

 

자기 자신을 제외하고, 모든 정점에 대해 비교가 가능한 학생이 자신의 키가 몇 번째인지 알 수 있는 학생이 된다.(모든 정점이 연결되어야함)

---

코드

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

int arr[501][501];

int main() {
	int n, m;
	cin >> n >> m;
	fill(&arr[0][0], &arr[500][501], INF);
	while (m--) {
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
	}
	for (int k = 1;k <= n;k++) {
		for (int i = 1;i <= n;i++) {
			for (int j = 1;j <= n;j++) {
				if (arr[i][k] == 1 && arr[k][j] == 1) arr[i][j] = 1;
			}
		}
	}
	int ans = 0;
	for (int i = 1;i <= n;i++) {
		int count = 0;
		for (int j = 1;j <= n;j++) {
			if (arr[i][j] == 1 || arr[j][i] == 1) count++;
		}
		if (count == n - 1) ans++;
	}
	cout << ans;
}