백준 6165 Cow Contest - C++, 플로이드-와샬

6156번: Cow Contest

#include <iostream>
#include <algorithm>
#define MAX 999999999
using namespace std;

int n, m, winner, loser, res = 0;
int compare[101][101];
int cow[101];

int main(){
    scanf("%d %d", &n ,& m);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            compare[i][j] = MAX;
    
    while(m--){
        scanf("%d %d", &winner, &loser);
        compare[winner][loser] = 1;
    }

    for(int via = 1; via <= n; via++){
        for(int from = 1; from <= n; from++){
            for(int to = 1; to <= n; to++){
                compare[from][to] = min(compare[from][to], compare[from][via] + compare[via][to]);
            }
        }
    }
    

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(compare[i][j] < MAX){
                cow[i]++;
                cow[j]++;

                if(cow[i] == n-1)
                    res++;
                if(cow[j] == n-1)
                    res++;
            }
                
        }
    }

    printf("%d\n", res);
}

---

 영어로 된 문제지만 해석은 간단했습니다. 한글문제로 비슷한건 2458번이 있었습니다.

 

 입력에 소의 갯수와 대전 횟수가 주어지게 되고 대전 횟수만큼 입력이 주어집니다. 입력의 순서는 [ 승자의 번호, 패자의 번호 ]이며 이를 통해 플로이드-와샬 알고리즘을 그대로 사용하면 됩니다. 그런 다음 2중 포문으로 소들의 대전 횟수를 체크한 다음 cow[i], i소의 대전 횟수가 n-1(자신 제외)라면 res값을 증가시켜 출력하면 됩니다.