BOJ - 2458번 키 순서 (Python)

문제 출처: https://www.acmicpc.net/problem/2458

난이도

Gold 4

풀이 방법

플로이드-와샬 알고리즘 사용

보통 위 알고리즘 같은 경우, A->C로 갈 때 B와 D로 거칠 수 있는지 여부와 방법의 수를 찾는데 쓰였는데 키 순서에 적용된다는 발상 전환이 되게 독특했다.
아마 문제 설명 속 1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 이라는 대목에서 힌트를 얻을 수 있을 것 같다.

A B C D E식의 순서로 되어 있는데 C가 5명 중 본인보다 큰 사람이 2명인 것을 알고 본인보다 작은 사람이 2명인것을 알면 키 순서 3등 이라는 것을 유추하기 쉽다. 이 문제에서는 이 관점을 사용해서 푸는데, 그럼 C가 자기보다 크고 작고를 어떻게 아는지를 판별해야한다. 이를 위해 플로이드 와샬을 쓰는 것이다.

통과 코드

import sys

if __name__ == '__main__':
    N,M = map(int,input().split())
    INF = sys.maxsize
    height = [[INF]*(N) for _ in range(N)]

    for _ in range(M):
        short, tall = map(int,input().split())
        height[tall-1][short-1] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if height[i][k] == 1 and height[k][j] == 1:
                    height[i][j] = 1

    count = [0]*(N)
    for i in range(N):
        for j in range(N):
            if height[i][j] == 1:
                count[i] += 1
                count[j] += 1

    print(count.count(N-1))

etc

사실 시간초과만 계속 나서 답답했다. 알고보니 Python3가 아닌 pypy3 형식으로 컴파일하면 통과가 됐다!
이 둘의 차이점이 궁금해서 찾아보니 둘은 동일한 문법을 제공하지만, pypy3이 python3보다 빠른 속도를 지녔다고 한다. 그래서 python3에서 시간초과 난다면 pypy3에서 한번 돌려보라고 추천하는 글을 보기도 했다.