[알고리즘] 백준 2458 - 키 순서

1. 문제

키 순서

 

2. 접근

1. 이번 키 문제는 이코테에 비슷한 문제가 있어서 생각을 해내는 것도 풀이를 하는 것도 편했다 ( 이코테 - 정확한 순위 )

2. n(노드)의 범위가 500이하 이므로 플라워드 - 워셜을 사용할 수 있는 조건을 만족한다

3. 기본적으로 플로이드-워셜은 2차원 배열을 초기화시키고, 같은 노드에서 같은 노드로 옮기면 거리는 0임을 알아야 한다

4. 문제에서 2사람 만을 비교하므로, 거리가 1이다.

5. a -> b or b -> a 이 모두 INF 가 아니라면 count 를 증가하여 result 값을 올려야 한다

 

 

3. 풀이

import sys
input = sys.stdin.readline

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

INF = int(1e9)

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

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0 # 같은 노드에서 같은 노드로 옮기면 거리가 0이다

for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1 # 두 사람만을 비교하므로, 거리가 1이다

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b]) # 기본 알고리즘

res = 0
for i in range(1, n+1):
    count = 0
    for j in range(1, n+1):
        if graph[i][j] != INF or graph[j][i] != INF: 둘 중하나라도 INF 아니면 count증가
            count += 1
    if count == n:
        res += 1
print(res)