[최단경로] 정확한 순위

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분

1. 문제 설명

- 학생들의 성적을 누구보다 높다, 낮다로만 나눌 때, 정확한 위치를 알 수 있는 학생의 수를 출력하는 문제

2. 접근 방식

- 플로이드 워셜 알고리즘을 사용한다.

- 단, 각 학생들별 연결을 확인할 때, graph[i][j]와 graph[j][i] 방향 모두를 확인해야 한다. (i -> j 방향, j -> i 방향)

3. 코드

n, m = map(int, input().split())
INF = 1e9
graph = [[INF]*(n+1) for _ in range(n+1)]

for a in range(1, n+1):
    graph[a][a] = 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):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
# 각 학생을 번호에 따라 한 명씩 확인하며 도달 가능한 지 체크한다.
# a -> b 방향뿐만 아니라, b -> a방향도 봐야 한다.
result = 0
for a in range(1, n+1):
    count = 0
    for b in range(1, n+1):
        if graph[a][b] != INF or graph[b][a] != INF:
            count +=1
    if count == n:
        result+=1
    print()
print(result)
"""
대략적인 graph 모양 (□: Node가 닿을 수 없는 곳)
■ ■ □ ■ ■ ■ 
■ ■ ■ ■ ■ □ 
□ ■ ■ ■ □ ■ 
■ ■ ■ ■ ■ ■ 
■ ■ □ ■ ■ ■ 
■ □ ■ ■ ■ ■ 
"""

4. 코멘트

- 처음에 플로이드로 구현했었는데, 두 방향을 고려한다는 걸 생각하지 못하고 다익스트라를 구현해봤었다.

- 이번 문제를 통해 플로이드 알고리즘을 돌려 나온 값을 이렇게도 활용할 수 있구나라는 생각을 했던 것 같다.