BOJ 2458 키 순서

사용한 알고리즘

플로이드 와샬

알고리즘 설명

자신의 키 순서를 알기 위해서는 모든 사람에 대해서 자신보다 키가 큰지 작은지를 알 수 있으면 된다.
일단 키에 대한 정보 (u->v)가 주어지면, (u->v)인 순방향 정보(키가 작은 순서)는 indeg 배열에, (v->u)인 역방향 정보(키가 큰 순서)는 outdeg 배열에 저장한다.
위 두 배열 indeg와 outdeg에 플로이드 와샬 알고리즘을 적용시켜 자신보다 키가 작은 사람(indeg)와 키가 큰 사람(outdeg)을 모두 알아낸다.
위 정보를 이용하면 자신보다 키가 작거나 큰 사람 관계를 알아 낼 수 있으며, 알아내지 못하는 경우에는 자신의 순위를 알 수 없는 경우이다.

풀이

// baekjoon 2458 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=501;

int N, M, u, v;
bool indeg[MAX_N][MAX_N], outdeg[MAX_N][MAX_N];

int main() {
	scanf("%d%d", &N, &M);
	// 자기 자신은 알 수 있음.
	for (int i=0; i<N; i++)
		indeg[i][i]=outdeg[i][i]=true;

	// 순방향과 역방향 간선 추가
	for (int i=0; i<M; i++) {
		scanf("%d%d", &u, &v);
		indeg[u-1][v-1]=true;
		outdeg[v-1][u-1]=true;
	}

	// 플로이드 와샬 알고리즘
	for (int k=0; k<N; k++) {
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				indeg[i][j] |= indeg[i][k] && indeg[k][j];
				outdeg[i][j] |= outdeg[i][k] && outdeg[k][j];
			}
		}
	}

	int cnt=0;
	for (int i=0; i<N; i++) {
		bool flag=false;
		for (int j=0; j<N; j++)
			// 자신(i)와 다른 사람(j) 간에 관계를 알 수 없는 경우
			if (!indeg[i][j] && !outdeg[i][j])
				flag=true;
		if (!flag)
			cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}