[이코테] 최단 경로_정확한 순위 (python)

문제

나의 풀이

1. 플로이드 와샬 알고리즘 수행

아이디어:

• 학생 수가 500명으로 적고, 도달 가능한지 보는거니까 플로이드 와샬
• 핵심: if graph[i][j] == graph[j][i] == INF
  • 다른 학생이 자기보다 성적이 낮거나 높은지 알 수 없는 경우에는, 순위는 알 수 없다

n, m = map(int, input().split()) # 학생 수, 성적 비교 횟수
INF = int(1e9)
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 경로를 담을 그래프
for i in range(1, n + 1):
    graph[i][i] = 0 # 자기 자신으로 가는 경로의 비용은 0
    
for _ in range(m): # i 성적 < j 성적
    i, j = map(int, input().split())
    graph[i][j] = 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])

# 자기보다 성적이 높은 학생에게 도달 가능하고(그래서 성적이 높은 학생 수를 알 수 있고),
# 자기보다 성적이 낮은 학생이 자기에게 도달 가능하면(그래서 성적이 낮은 학생 수를 알 수 있으면) 정확한 순위를 알 수 있다.
# 즉, 자기보다 성적이 낮은 학생 수 + 자기보다 성적이 높은 학생 수 = 총 학생 수 이어야 한다.
cnt = 0
for i in range(1, n + 1):
    possible = True # 순위를 알 수 있다고 가정하고
    for j in range(1, n + 1):
        if graph[i][j] == graph[j][i] == INF: # 자기보다 성적이 낮거나 높은지 알 수 없는 경우
            possible = False # 순위를 알 수 없음!
            break
    if possible: # 순위를 알 수 있다면
        cnt += 1 # 정답 1명 증가
print(cnt)