[플로이드워샬] 백준 2458 Gold4 키순서

📌 링크 : https://www.acmicpc.net/problem/2458

2458번: 키 순서

❗️ Issue 

1️⃣  "플로이드 워샬을 써야함+본인 빼고 다른 친구들과 연결되어야 순서를 알 수 있음" 은 알겠는데 어떻게 구하지?

💡 Solution 

1️⃣ 본인 빼고 다른 친구들과 연결되어야 순서를 알 수 있음 => graph[i][j] + graph[j][i] 를 모든 친구 j 에 대해서 수행한 후 더해서

n-1이 나오면 순서를 알 수 있음 , 이러려면 초기화를 0으로 해야함 (INF X)

2️⃣ 플로이드 워샬을 써야함 => 연결이 되어 있다면 1로 표기 if graph[a][k] == 1 and graph[k][b] ==1 : graph[a][b] =1

 

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

graph = [[0]*(n+1) for _ in range(n+1)]

for i in range(1, n+1):
    graph[i][i] = 0

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            if graph[a][k] == 1 and graph[k][b] == 1:
                graph[a][b] = 1

answer = 0
for i in range(1, n+1):
    check = 0
    for j in range(1, n+1):
        check += (graph[i][j] + graph[j][i])
    if check == (n-1):
        answer += 1

print(answer)