백준 2458 키 순서

작성일 | In |

문제 링크


알고리즘

  • 그래프
  • 플로이드-와샬


비슷한 문제


풀이

모두 키가 다르다는 전제 하에 풀 수 있다.

플로이드-와샬 알고리즘을 이해하는 것이 중요하다. 설명은 코드에 주석으로 달았다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
# input = sys.stdin.readline

n, m = map(int, input().split())

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

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

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

for k in range(1, n+1):  # k 번 돌려준다.
    for i in range(1, n+1):
        for j in range(1, n+1):
            if height[i][k] + height[k][j] == 2:   # i가 k보다 작고, k가 j보다 작으면 당연히 i는 j보다 작다는 사실을 알 수 있다.
                height[i][j] = 1
                

count = 0
for i in range(1, n+1):
    total = 0
    
    for j in range(1, n+1):
        total += height[i][j] + height[j][i] # 자신보다 키가 작은 사람 수 + 자신보다 키가 큰 사람 수.
        
    if total == n-1: # 그러니까 자기보다 키가 작은 사람과 큰 사람 수를 합쳤을 때 n-1명이면 당연히 자기의 키 순서를 알 수 있다.
        count += 1
        
print(count)