[플로이드-와샬] BOJ 2458 키 순서

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

2458번: 키 순서

 

문제 해결 알고리즘

 

플로이드 와샬 응용 문제

 

플로이드 와샬로 각 노드에서 노드로 가는 배열들을 모두 구한 후 그 배열에서 INF값이 아닌 값들의 개수를 따로 구해주어서 그 값보다 작거나 같은 값의 개수가 그 값과 같다면 자신의 키가 몇 번째인지 알 수있는 학생이다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int N, M;
int arr[501][501];
int d[501];

void floyd(){

    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(arr[i][j] > arr[i][k] + arr[k][j]) arr[i][j] = arr[i][k] + arr[k][j];
            }
        }
    }
}

int main(){ 
    cin >> N >> M;

    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++){
            arr[i][j] = INF;
        }
    }
    
    int a, b; 
    for(int i=0;i<M;i++){
        cin >> a >> b;
        arr[a][b] = 1;
    } 

    floyd();
    
    for(int i=1;i<=N;i++) {
        int cnt = 0;
        for(int j=1;j<=N;j++){
            if(arr[i][j] != INF) cnt++;
        }
        d[i] = cnt;
    }

    int ans = 0;

    for(int i=1;i<=N;i++){
        int cnt = 0;
        for(int j=1;j<=N;j++){
            if(i == j) continue;

            if(d[i] >= d[j]) cnt++;
        }

        if(cnt == d[i]) ans++;
    }
    
    cout << ans;
}