정확한 순위 코드 및 해설 (파이썬)

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 38, p 386

 

플로이드 워샬 알고리즘을 활용해 풀이했습니다. 현재 학생을 제외한 나머지 학생들이 현재 학생보다 성적이 낮은지, 높은지 모두 알면 그 학생의 정확한 순위를 알 수 있습니다.

 

A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 하면, 플로이드 워샬 알고리즘 수행 후 그래프의 n번째 가로줄(행)에 INF가 아닌 숫자가 있으면 그 인덱스의 학생은 n번째 학생보다 성적이 높다는 의미입니다. n번째 세로줄(열)에 INF가 아닌 숫자가 있으면,  그 인덱스의 학생은 n번째 학생보다 성적이 낮다는 의미입니다. 

 

따라서 n번째 행과 열에서 INF가 아닌 값을 가지는 인덱스 + 자기 자신의 인덱스(n)을 합쳤을 때, 1 ~ N(전체 학생 수)이 모두 포함되면 n번째 학생은 정확한 순위를 알 수 있습니다. 

 

import sys

INF = int(1e9)

# 입력 받아오기 
inputs = list(map(int, sys.stdin.read().split()))
# 학생 수 
N = inputs[0]
# 비교한 결과의 수 
M = inputs[1]
# 성적 비교 결과 
scores = inputs[2:]

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

for i in range(0, len(scores), 2):
    low, high = scores[i], scores[i+1]
    graph[low][high] = 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])
            
answer = []
for n in range(1, N+1):
    transposedGraph = list(zip(*graph))
    # 그래프의 n번째 가로줄, n번째 세로줄에서 0이 아닌 index들 + 자기 자신의 index를 합치면 1 ~ N이 되는 경우 순위를 알 수 있음 
    if set([i for i,x in enumerate(graph[n]) if x != INF] + [i for i,x in enumerate(transposedGraph[n]) if x != INF] + [n]) == set(range(1,N+1)):
        answer.append(n)

# 순위를 알 수 있는 학생의 수  
print(len(answer))