[K 대회] 정확한 순위

문제

 선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다.

학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과입니다.

 

- 1번 학생의 성적 < 5번 학생의 성적

- 3번 학생의 성적 < 4번 학생의 성적

- 4번 학생의 성적 < 2번 학생의 성적

- 4번 학생의 성적 < 6번 학생의 성적

- 5번 학생의 성적 < 2번 학생의 성적

- 5번 학생의 성적 < 4번 학생의 성적

 

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

 

입력 조건

- 첫째 줄에 학생들의 수 N(2 <= N <= 500)과 두 학생의 성적을 비교한 횟수 M(2 <= M <= 10,000)이 주어집니다.

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

 

출력 조건

- 첫째 줄에 성적 순위를 정확히 알 수 있는 학생이 몇 명인지 출력합니다.

 

입력 예시

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

 

출력 예시

1

---

아이디어

 만약 4번 학생의 순위를 정확히 알 수 있다면, 그 말은 즉슨 4번 학생보다 점수가 높은 학생이 몇 명인지, 또 4번 학생보다 점수가 낮은 학생은 몇 명인지 정확히 구할 수 있다는 이야기입니다. 따라서 플로이드-워셜 알고리즘을 이용하여 최단거리 그래프를 만든 뒤 해당 노드를 제외한 모든 노드에 대해서 '연결하거나 연결되고 있다'면 해당 노드는 성적 순위를 정확히 알 수 있는 노드입니다.

 

 전체 소스코드는 다음과 같습니다.

n, m = list(map(int, input().split()))
array = []
for _ in range(m):
    array.append(input())
    
INF = int(1e9)

graph = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    graph[i][i] = 0
    
for x in array:
    s, e = list(map(int, x.split()))
    graph[s][e] = 1
    
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
            
table = [False] * (n + 1)
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] == INF and graph[j][i] == INF:
            break
    else:
        table[i] = True
        
print(sum(table))

 

 다른 부분은 일반적인 플로이드-워셜 알고리즘을 따르지만, 마지막 부분이 중요합니다. 업데이트가 완료된 그래프에 대해서 각 노드에 대해 '연결되거나 연결할 수 있는지를 따져 table 변수에 boolean 형태로 삽입합니다. 마지막에 table 리스트에 대해서 sum을 해주면 전체 True의 갯수를 구할 수 있습니다.

table = [False] * (n + 1)
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] == INF and graph[j][i] == INF:
            break
    else:
        table[i] = True
        
print(sum(table))