[백준 2458] 키 순서 (python)

2458번: 키 순서

---

 

플로이드 워셜을 이용하자!

 

1. arr[i][j]는 i키 < j키라면 1을 넣어준다.
2. i키 < k키 , k키 < j키 라면 i키 < j키 이므로 플로이드 워셜을 통해 arr를 업데이트 해준다.
3. arr[i][j] 또는 arr[j][i]가 1이라면 i와 j의 대소관계를 파악할 수 있다.
4. 대소관계를 파악할 수 있는 사람의 수를 세어 본인을 제외한 나머지(N-1)라면 카운트 해준다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    s, e = map(int, input().split())
    arr[s][e] = 1

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if arr[i][k] == arr[k][j] == 1:
                arr[i][j] = 1

result = 0
for i in range(1, N+1):
    cnt = 0
    for j in range(1, N+1):
        cnt += arr[i][j] + arr[j][i]
    if cnt == N-1:
        result += 1

print(result)