[Python] BOJ/백준 2458번 키 순서

[문제]

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

2458번: 키 순서

 

[풀이]

두 학생 a, b를 a가 b를 향하는 방향 그래프로 나타내면 키의 크고 작음을 표시할 수 있다.

플로이드-와샬 알고리즘을 통해 한 정점에서부터 모든 정점으로의 연결 상태를 알아내어 그래프를 갱신한다.

왼쪽 리스트는 예제 2번 문제를 플로이드-와샬 알고리즘을 통해 그래프를 갱신한 상태이다. 위 그림의 1번 노드는 다른 정점을 통해 모든 정점으로 연결될 수 있기 때문에 리스트[0] 은 자기 자신을 제외하고 전부 1이다.

2번 노드는 자신으로부터 출발하는 정점이 없기 때문에 리스트[1] 은 전부 0의 값을 가진다.

 

이런식으로 각 노드와 연결된 노드의 개수가 N - 1이라면 해당 노드가 몇 번째인지 알 수 있다.

 

 

 

+ 이 문제는 pypy3으로 제출해야 통과된다.

++ 플로이드-와샬 알고리즘을 각 정점에서 다른 모든 정점으로 연결됐는지 여부를 확인하는 용도로는 처음 써보았다.

 

 

[코드]

from sys import stdin

input = stdin.readline
N, M = map(int, input().split())
student = [([0] * N) for _ in range(N)]
for _ in range(M):
    small, tall = map(int, input().split())
    student[small-1][tall-1] = 1

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

answer = 0
for i in range(N):
    check = 0
    for j in range(N):
        check += student[i][j] + student[j][i]
    if check == (N - 1):
        answer += 1
print(answer)