BOJ 6156 - Cow Contest

문제

백준 온라인 저지 - 6156번

풀이 과정

두 소들 간의 싸움 경기 결과가 주어질 때 순위를 결정할 수 있는 소들의 수를 구하는 문제입니다.

특정 소의 순위를 결정하기 위해서는 해당 소에게 진 소들의 수와 해당 소를 이긴 소들의 합이 N - 1 이어야 합니다.
때문에 각 소들을 그래프의 정점이라고 생각한다면 모든 소들 사이의 도달 가능성을 플로이드 와샬 알고리즘을 이용해 파악하고
각 소들에 대해서 특정 소 A 에 도달 가능한 정점의 수와 A 에서 도달 가능한 소들의 수를 세어주면 됩니다.

코드

import sys

N, M = list(map(int, sys.stdin.readline().split()))
results = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]


def make_dist():
    dist = [[0] * N for _ in range(N)]

    for winner, loser in results:
        dist[loser - 1][winner - 1] = 1

    return dist


def floyd(dist):
    for v in range(N):
        dist[v][v] = 1

    for k in range(N):
        for u in range(N):
            for v in range(N):
                dist[u][v] = dist[u][v] or (dist[u][k] and dist[k][v])

    determined = 0

    for v in range(N):
        reachable = 0
        for to in range(N):
            if dist[v][to] and to != v:
                reachable += 1
        for frm in range(N):
            if dist[frm][v] and frm != v:
                reachable += 1

        if reachable == N - 1:
            determined += 1

    return determined


def solution():
    dist = make_dist()
    answer = floyd(dist)

    return answer


print(solution())