카테고리 없음

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

영최 2023. 12. 13. 16:33
728x90

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

 

2458번: 키 순서

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여

www.acmicpc.net

❗️ 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)
728x90