[이코테] 정확한 순위

문제

선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 ㅂ교한 결과입니다.

• 1번 학생의 성적 < 5번 학생의 성적
• 3번 학생의 성적 < 4번 학생의 성적
• 4번 학생의 성적 < 2번 학생의 성적
• 4번 학생의 성적 < 6번 학생의 성적
• 5번 학생의 성적 < 2번 학생의 성적
• 5번 학생의 성적 < 4번 학생의 성적

A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 할 때 성적 결과를 다음 그림처럼 표현할 수 있습니다.

이 그림으로 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮습니다. 따라서 1번, 3번, 5번 학생은 모두 4번 학생보다 성적이 낮다고 볼 수 있습니다. 그리고 4번 학생은 2번 학생과 6번 학생보다 성적이 낮습니다. 정리하면 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 정확히 ㅏㅇㄹ 수 있습니다. 하지만 예시에서 4번 학생을 제외한 다른 학생은 정확한 순위를 알 수 없습니다.

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

입력 조건

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

다음 M개의 각 줄에는 두 학생의 성적을 비교한 겨로가를 나타내는 두 양의 정수 A와 b가 주어집니다.

이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미합니다.

출력 조건

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

입출력 예

Example 1:

Input: 
6 6
1 5
3 4
4 2
4 6
5 2
5 4
Output: 
1

풀이과정

내풀이

# 무한대 정의
INF = int(1e9)

# n = 학생들의 수, m = 두 학생의 성적을 비교한 횟수
n, m = map(int,input().split())

# 성적 비교 정보 기록
graph = [[INF]*(n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = min(graph[a][b], 1)
    
# 자기 자신으로 갈 때 초기화
for i in range(1, n + 1):
    graph[i][i] = 0
    
# 플로이드-워셜 알고리즘 적용
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):
  sub = 0
  for j in range(1, n + 1):
    if graph[i][j] != INF or graph[j][i] != INF:
      sub += 1
  if sub == n:
    cnt += 1
print(cnt)

책 풀이

이 문제는 최단 경로를 계산하는 문제로 볼 수 있다. 문제에서도 나와 있듯이 학생들의 성적을 비교한 결과를 방향 그래프 형태로 표현할 수 있다. 성적이 낮은 학생이 성적이 높은 학생을 가리키는 방향 그래프로 표현할 수 있으므로, 최단 경로 알고리즘을 수행할 수 있게 된다.

A번 학생과 B번 학생의 성적을 비교할 때, ‘경로’를 이용하여 성적 비교 결과를 알 수 있다. A에서 B로 도달이 가능하다는 것은, A가 B보다 성적이 낮다는 의미가 된다. 따라서 A에서 B로 도달이 가능하거나, B에서 A로 도달이 가능하면 ‘성적 비교’가 가능한 것이다. 반대로 A에서 B로 도달이 불가능하며, B에서 A로도 도달이 불가능하다면, ‘성적 비교 결과를 알 수 없는’경우가 되는 것이다.

이 문제에서는 학생의 수 N이 500 이하의 정수이므로 $O(N^3)$의 시간 복잡도로 동작하는 플로이드 워셜 알고리즘을 이용해 문제를 해결할 수 있다. 따라서 플로이드 워셜 알고리즘을 수행한 뒤에, 모든 노드에 대하여 다른 노드와 서로 도달이 가능한지를 체크하여 문제를 해결할 수 있다. 이때 자기 자신은 항상 도달이 가능하다고 보고, 카운트를 진행한다. 결과적으로 특정한 노드의 카운트 값이 N이라면, 해당 노드의 정확한 순위를 알 수 있다는 것을 의미한다.

INF = int(1e9) # 무한을 의마하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0
            
# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용을 1로 설정
    a, b = map(int, input().split())
    graph[a][b] = 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])
            
result = 0
# 각 학생을 번호에 따라 한 명씩 확인하며 도달 가능한지 체크
for i in range(1, n + 1):
    count = 0
    for j in range(1, n + 1):
        if graph[i][j] != INF or graph[j][i] != INF:
            count += 1
    if count == n:
        result += 1
print(result)