[코테 스터디] 최단 경로, 정확한 순위

Q38. 정확한 순위

🐣문제

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

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

A번 학생의 성적이 B번 학생보다 낮다면 A->B로 표현할 수 있다.

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


입력 조건
첫째 줄에 학생 수와 비교 수가 주어진다.
다음 비교 수만큼 A와 B가 주어지는데, A가 B보다 낮다는 것을 의미한다.


입력 예시
6 6
1 5
3 4
4 2
4 6
5 2
5 4


출력 예시
1

🐥풀이

다익스트라와 플로이드 워셜 알고리즘을 사용하여 풀 수 있다.

다익스트라
이전 문제에서 언급했 듯, 출발 노드에서 도착 노드까지의 최단 거리를 거리 테이블을 활용하여 구한다.

플로이드 워셜
다익스트라를 활용하여 구한 최단 거리의 모든 경우의 수를 구한다.


알고리즘을 사용할 방법만 깨달으면 다음부터는 간단하다.
한 학생의 성적 순위를 정확히 알기 위해서는 나머지 학생들과의 모든 비교가 가능하면 정확한 순위를 알 수 있다.


따라서 다익스트라와 플로이드 워셜을 활용하여 나머지 학생과의 비교가 전부 가능한지 (즉, 거리 테이블에서 0 또는 무한대가 아닌 최단 거리가 나왔는지)를 확인하여 가능하면 해당 학생은 정확한 순위를 알 수 있는 것으로 판단할 수 있다.

위 과정을 반복하여 정확한 순위를 알 수 있는 학생의 수를 구하여 출력한다.

🐓코드

import heapq

# 입력값
n, m = map(int, input().split())  # 학생 수, 성적 비교 수
graph = [[] for _ in range(n+1)]
for _ in range(m):
  a, b = map(int, input().split())  # a < b
  graph[a].append(b)  # a -> b

  
# 거리 테이블 초기화
distance = [int(1e9)]*(n+1)


# 다익스트라
def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  
  while q:
    cost, student = heapq.heappop(q)
    
    if distance[student]<cost:
      continue
      
    for g in graph[student]:
      if distance[g] > cost+1:
        distance[g] = cost+1  # 거리비용 업데이트
        heapq.heappush(q, (cost+1, g))


# 플로이드 워셜
result = []
for i in range(1, n+1):
  dijkstra(i)
  result.append(distance[1:])
  distance = [int(1e9)]*(n+1)


std = 0
for i in range(n):
  count = 0
  
  for j in range(n):
    # 자기 자신을 제외하고 다른 학생 (n-1)명과의 점수 비교만 되면 정확한 순위 가능
    # 0이나 int(1e9)가 아니면 비교 가능 (즉, 연결되어 있으면 비교 가능)
    if (result[i][j]!=0 and result[i][j]!=int(1e9)) or (result[j][i]!=0 and result[j][i]!=int(1e9)):
      count += 1
      
  if count==n-1:
    std += 1

print(std)

⭐2022.05.11

알고리즘과 활용 방식만 알면 구현 문제는 쉬웠던 문제! 근데 그 풀이방식을 세우기가 어려웠지 ㅠㅠ