[백준] 2458 키 순서 - Python

📖 문제

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

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산

💻 내 코드

import sys

N, M = map(int, sys.stdin.readline().split())

students = [[0 for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    students[b][a] = 1

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if students[i][k] == 1 and students[k][j] == 1:
            # 자신(k)보다 작고 큰 학생의 정보가 모두 있다면
                students[i][j] = 1

answer = 0
for i in range(1, N+1):
    res = 0
    for j in range(1, N+1):
        res+=students[i][j]+students[j][i]
    if res==(N-1):
    	# 자신보다 작은 학생과 큰 학생을 모두 알 수 있다는 뜻
        answer+=1

print(answer)

💡 풀이

• 자신보다 작은 학생의 수와 큰 학생의 수를 더했을 때 N-1이라면 몇 번째인지 확인이 가능
• 플로이드-워셜을 사용해서 이를 확인
  • i->k, k->j 가 가능하다면 i->j 또한 가능
• 다른 학생에게 갈 수 있는 경로가 모두 존재하면 키 순서 확인 가능