정확한 순위

 

 

유형 파악 및 구현

이 문제는 B의 성적이 A의 성적이 높다 와 같은 정보들이 주어진다. 이를 활용해 성적 순위를 알 수 있는 학생의 수를 출력하는 것이다.

예를 들어,

5는 1보다 성적이 높다

4는 3보다 성적이 높다

2는 4보다 성적이 높다

6는 4보다 성적이 높다

2는 5보다 성적이 높다

5는 4보다 성적이 높다

라는 정보가 주어진다고 가정할 때, 순위를 알 수 있는 학생의 수를 구하는 것이다.

 

이를 해결하기 위한 전제 조건은 다음과 같다.

"A가 B보다 높은지, B가 A보다 높은지 모르겠으면 비교가 불가능한 쌍이 된다"

이는 정확히 순위를 구하는 것이 아닌 순위를 알 수 있는 학생의 수를 구하는 문제이기에 가능하다.

 

이를 구현할때는 플로이드 워셜 알고리즘을 통해 모든 학생에서 모든 학생으로 가는 최단. 경로를 구해서 구현한다.

 

 

코드

n = 6
m = 6
INF = int(1e9)
graph = [[INF]*(n+1) for _ in range(n+1)]

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

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


for k in range(1, n+1):
    for x in range(1, n+1):
        for y in range(1, n+1):
            graph[x][y] = min(graph[x][y], graph[x][k]+graph[k][y])


count = [True]*(n+1)
count[0] = False
for x in range(1, n+1):
    for y in range(1, n+1):
        if graph[x][y] == INF and graph[y][x] == INF:
            count[x] = False
            count[y] = False

for i in graph:
    print(i)

final_count = 0
for i in count:
    if i == True:
        final_count += 1
print(final_count)