[Python] 백준 2458번 : 키 순서

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

2458번: 키 순서

---

💡 문제 풀이

플로이드-워샬 알고리즘 문제이다.

 

특정 경로로 이동할 수 있는지 여부를 플로이드-워샬로 처리하고 값을 따진다.

여기서 자기 키 순서는 (자기보다 작은 사람 수 + 자기보다 큰 사람 수) == N-1 이면 알 수 있다.

예를 들어서, 6명이 있다면 작은 사람이 3명, 큰 사람이 2명 있다면 자기 키 순서는 3등이라는 것을 알 수 있다.

✔️ 느낀 점

안 좋아하는 유형의 문제라서 30분을 꼬박 고민하고 결국 답을 찾아서 봤다. 플로이드 워샬 자체만 잘 기억해두자.

💻 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[False] * (N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = True
    
for k in range(1, N+1):
    for x in range(1, N+1):
        for y in range(1, N+1):
            if graph[x][k] and graph[k][y]:
                graph[x][y] = True

ans = 0
for x in range(1, N+1):
    cnt = 0
    for y in range(1, N+1):
        if graph[x][y]: cnt +=1
        if graph[y][x]: cnt +=1
    if cnt == N-1: ans+=1
    
print(ans)