최단 거리 알고리즘

• 다익스트라 알고리즘
  그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 플로이드 워셜 알고리즘
  모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
• 벨만 포드 알고리즘

✅ 문제

학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성하세요.

첫째 줄에 학생들의 수 N, 두 학생의 성적을 비교한 횟수 M
다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A와 B가 주어집니다. 이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미합니다.

입력 예시

6 6
1 5
3 4
4 2
4 6
5 2
5 4

출력 예시

1

💻 코드

INF = int(1e9)
N, M = map(int, input().split())

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

for i in range(M):
    A, B = map(int, input().split())
    graph[A][B] = 1

for i in range(1, N + 1):
    for j in range(1, N +1):
        if i == j:
            graph[i][j] = 0

for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

result = 0
count = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if (graph[i][j] != 0 and graph[i][j] != INF) or (graph[j][i] != 0 and graph[j][i] != INF):
            count += 1  
    if count == N - 1:
        result += 1
    count = 0

print(result)
        

설계

플로이드 워셜 알고리즘을 이용하여 문제를 풀었다. 플로이드 워셜 알고리즘은 모든 지점에서 다른 지점들까지 연결되어 있는지 알 수 있기 때문에, graph(graph[N][N] 1 <= n <= N)의 n행에서 0 또는 INF 값을 가지지 않은 학생은 n의 성적보다 높은 학생을 나타내고 n열은 n보다 성적이 낮은 학생을 나타낸다. 따라서 n행과 n열에 연결되어 있는 학생의 수가 N - 1이면 순위를 정확히 알 수 있다.

📝 정리

너무 오래 고민했다...