[백준 / Python] 2458 키 순서 (플로이드-와샬 알고리즘)

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

결과

• 메모리: 126508 KB
• 시간: 976 ms

해결 방식

• 도저히 모르겠어서 블로그를 찾아봤다. (감사합니다 ㅎ.ㅎ)
  https://chldkato.tistory.com/42
• 아직 플로이드의 원리를 제대로 파악하지 못해서 그런 것 같다. 제대로 이해하고 풀자.
• key: 자신의 정점으로 오는 경로가 모두 파악된 것만이 자신의 키가 몇 번째인지 알 수 있다. 라는 것이다.

알게된 것

• print([1, 2, 3, 3].count(3)) # count 함수
• 플로이드-와샬 알고리즘을 3번째 푸는데, 점점 감이 잡힌다!

from sys import maxsize

n, m = map(int, input().split())
arr = [[maxsize] * (n + 1) for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    arr[a][b] = 1

def printArr(a):
    for i in a:
        for j in i:
            print(j, end=' ')
        print()

def floyd():
    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] == 2:
                    arr[i][j] = 1
floyd()

cnt = [0] * (n + 1)
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if arr[i][j] == 1:
            cnt[i] += 1
            cnt[j] += 1
print(cnt.count(n - 1))