c언어 2458번 키 순서 (백준)

#include <stdio.h>
#define INF 10000000

int main(void) { //단방향 그래프
	int n, m;
	scanf("%d %d", &n, &m);
	int d[501][501]; //최단거리를 담는 배열
	for(int i = 1; i<=n; i++) { //최단거리를 INF로 초기화
		for(int j=1; j<=n; j++) d[i][j] = INF;
		d[i][i] = 0; //자기자신은 0
	}
	
	while(m--) { //정보 입력
		int a, b;
		scanf("%d %d", &a, &b);
		d[a][b] = 1;
	}
	
	for(int k=1; k<=n; k++) //Floyd Warshall
	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++) {
		if(d[i][k] + d[k][j] < d[i][j])
		d[i][j] = d[i][k] + d[k][j];
	}
	
	int sum[501] = {0}; //각 사람에 대한 연결된 그래프의 총합
	int ans = 0; 
	for(int i = 1; i<=n; i++) { //연결된 그래프 세기
		for(int j=1; j<=n; j++) {
			if(d[i][j] < INF) {
				sum[i]++;
				sum[j]++;
			}
		}
	for(int i = 1; i<=n; i++) { //연결된 그래프가 n+1이면 그 사람은 다른 모든 사람들과 연결 되었다는 의미
		if(sum[i] == n+1) ans++; //n+1인 이유는 위의 연결된 그래프 세기에서 자기자신의 경우 +2가 되기 때문
	}
	
	printf("%d", ans);
}

풀이 : Floyd Warshall

0) 입력을 받는다

1) 최단 거리 배열을 INF로 초기화한다 (자기 자신은 거리가 0인 그래프가 있다고 가정)

2) 정보들을 입력 받는다, 그때의 거리는 1로 한다.

3) Floyd Warshall

4) 거리가 INF가 아니라면, 이는 서로가 그래프로 연결되어 있다는 의미이므로, 몇 개가 연결되어있는지를 구한다.

5) 만약 n+1개 가 연결되어 있다면 (원래는 n-1이나, 자기자신을 연결하는 그래프를 계산하면 +2가 된다)

6) 그래프가 n+1 연결 된 것의 개수의 합을 출력한다.

 

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

2458번: 키 순서