[백준 3665번] 최종 순위 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

def makerank():
  seq = []
  dq = deque()
  for i in range(1,N+1):
    if indegree[i] == 0:
      dq.append(i)
  while dq:
    if len(dq) > 1:
      return "?"
    x = dq.popleft()
    seq.append(x)
    for c in child[x]:
      indegree[c] -= 1
      if indegree[c] == 0:
        dq.append(c)
  if len(seq) != N:
    return "IMPOSSIBLE"
  return " ".join(map(str,seq))

T = int(input())
for _ in range(T):
  N = int(input())
  lastyear = [*map(int,input().split())]
  child = {i:set() for i in range(1,N+1)}
  indegree = {i:0 for i in range(1,N+1)}
  for i in range(N):
    for j in range(i+1,N):
      child[lastyear[i]].add(lastyear[j])
      indegree[lastyear[j]] += 1
    
  M = int(input()) 
  for _ in range(M):
    a,b = map(int,input().split())
    if b in child[a]:
      child[a].remove(b)
      child[b].add(a)
      indegree[a] += 1
      indegree[b] -= 1
    else:
      child[b].remove(a)
      child[a].add(b)
      indegree[b] += 1
      indegree[a] -= 1

  print(makerank())

전형적인 위상정렬 문제이다.

 

알고리즘을 요약하면

1. 작년의 데이터를 기준으로 i등의 번호에 대해 i+1~N등까지 전부 i등 번호의 후순위로 저장하고, 후순위 번호들의 indegree를 1씩 늘려준다.

2. 등수가 바뀐 번호에 대하여 a가 원래 b보다 높은 순위였다면 a의 후순위 목록에서 b를 지우고 b의 후순위 목록에 a를 추가한 후 indegree를 +1, -1씩 해준다.

3. 위상정렬을 실행한다. 이때 dq에 요소가 2개 이상 들어가면 명확한 순위를 알 수 없으므로 "?"를 출력한다.

4. 위상정렬이 끝났는데 모든 요소가 배열되지 않았다면 "IMPOSSIBLE"을 출력한다.

 

 

처음에는 바뀐 데이터만 사용해서 문제를 풀어야한다고 생각했다가 작년의 데이터도 이용해야 한다는 사실을 알게되었다.

위상정렬 알고리즘을 알고있다면 쉽게 풀 수 있는 문제

 

 

오늘의 교훈) 위상정렬은 유용하다.