BOJ 2458 - 키 순서

문제

백준 온라인 저지 - 2458번

풀이 과정

학생들의 키 차이 관계가 주어질 때 자신의 키 순서를 파악할 수 있는 학생의 수를 찾는 문제입니다.

키 순서를 파악하기 위해서는 자신을 제외한 모든 학생들과의 대소 관계를 파악할 수 있어야 합니다.
때문에 N 명의 학생들을 그래프의 정점, 학생들 사이의 키 정보를 간선이라고 하면
한 학생이 다른 모든 학생에 도달 가능하거나 다른 학생으로부터 해당 학생으로 도달 가능한 총 인원이 N - 1 이어야 합니다.
플로이드 와샬 알고리즘을 활용해서 모든 학생들 사이의 도달 가능성을 파악하면 문제를 해결할 수 있습니다.

코드

import sys

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


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

    for frm, to in edges:
        dist[frm - 1][to - 1] = 1

    return dist


def floyd(dist):
    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])


def solution():
    dist = make_graph()
    floyd(dist)
    answer = 0

    for frm in range(N):
        acc = 0

        for to in range(N):
            if dist[frm][to] or dist[to][frm]:
                acc += 1

        if acc == N - 1:
            answer += 1

    return answer


print(solution())