[백준] 2458번 - 키 순서 (파이썬)

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

# 키 순서
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):
    a, b = map(int, input().split())
    arr[a][b] = 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][j] == 0:
                if arr[i][k] == 1 and arr[k][j] == 1:
                    arr[i][j] = 1

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

 

최단거리, 플로이드와샬 알고리즘

1. 입력을 받으면서 NxN배열에 1로 초기화

2. 플로이드-와샬 (목표노드 까지 다른 노드를 거쳐서 갈 수 있으면 1)

3. (i)노드에서 다른 노드들로 가는 값들과 다른 노드들에서 (i)노드로 갈 수 있는 값을 모두 합 == N-1이면 result +=1

4. result 출력

 

위상정렬인줄 알았는데 순서를 출력하는게 아닌 자기 순서를 알고있는 학생 수를 출력하는 것이였다.

3번에 합이 N-1일 경우 자기 자신을 뺀 모든 노드와 연결이 된 상태라는 것 즉 자신의 위치를 알고 있다는 것이다.