BOJ 6156 - Cow Contest 링크
(2023.07.06 기준 G4)

문제

N마리의 소들이 프로그래밍 대회에 참가한다. 소들의 가능한 모든 쌍이 대결을 하며, 각 소들은 기술 수준이 정해져 있고 기술 수준이 높은 소가 항상 이긴다.
M개의 대결 결과가 주어질 때, 정확하게 순위를 알 수 있는 소의 마릿수 출력

알고리즘

플로이드 워셜 응용

풀이

N 크기의 정방행렬을 0으로 초기화하여 만들어주자. 그리고 주어지는 M개의 대결에서 소 A가 소 B를 이기면 matrix[A][B] = 1로 저장하자.

소 A가 소 B를 이기고 소 B가 소 C를 이기면, 소 A는 항상 소 C를 이긴다.
이를 플로이드 워셜로 나타내자.

그럼 이제 순위를 결정할 수 있는 소는 어떻게 알 수 있을까?
플로이드 워셜을 돌리면 직간접적으로 승패를 알 수 있는 모든 경우는 저장되어 있다.
이제 모든 소마다, 자기 자신을 제외한 모든 소에 대한 승패 결과를 알 수 있는 소 마릿수를 세어 N - 1개면. 즉, 모든 소에 대한 승패 결과를 알 수 있으면 순위를 결정할 수 있다.

코드

• C++

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;

    int matrix[N][N]; fill(&matrix[0][0], &matrix[N - 1][N], 0);
    for (int i = 0, A, B; i < M; i++){
        cin >> A >> B;
        matrix[--A][--B] = 1; // A가 B를 이김을 나타낸다.
    }

    for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        // i가 k를 이기고 k가 j를 이기면 결국 i는 j를 이긴다.
        if (matrix[i][k] && matrix[k][j]) matrix[i][j] = 1;

    int result = 0;
    for (int i = 0; i < N; i++){
        int ct = 0;
        // i가 j를 이기거나 j한테 지는지 확인
        for (int j = 0; j < N; j++)
            if (matrix[i][j] || matrix[j][i]) ct++;
        // 자기 자신을 제외한 모든 소에 대한 승패 결과를 알 수 있다면 순위를 결정할 수 있다.
        if (ct == N - 1) result++;
    }

    cout << result;
}

• Python

import sys; input = sys.stdin.readline

N, M = map(int, input().split())

matrix = [[0] * N for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    matrix[A - 1][B - 1] = 1 # A가 B를 이김을 나타낸다.

for k in range(N):
    for i in range(N):
        for j in range(N):
            # i가 k를 이기고 k가 j를 이기면 결국 i는 j를 이긴다.
            if matrix[i][k] and matrix[k][j]:
                matrix[i][j] = 1

result = 0
for i in range(N):
    ct = 0
    for j in range(N):
        # i가 j를 이기거나 j한테 지는지 확인
        if matrix[i][j] or matrix[j][i]:
            ct += 1
    # 자기 자신을 제외한 모든 소에 대한 승패 결과를 알 수 있다면 순위를 결정할 수 있다.
    if ct == N - 1:
        result += 1

print(result)