[백준] 3665번: 최종 순위 - 파이썬(python)

 

 

나의 풀이

from collections import deque

T = int(input())
for _ in range(T):
  n = int(input())
  graph = [[False]*(n+1) for _ in range(n+1)] 
  last_year = list(map(int, input().split())) # 작년의 순위
  indegree = [0] * (n+1) # 진입차수

  for i in range(n):
    for j in range(i+1,n) :
      graph[last_year[i]][last_year[j]] = True 
      indegree[last_year[j]] += 1 # j의 진입차수 1증가
  
  m = int(input()) # 상대적인 등수가 바뀐 쌍의 수
  for i in range(m) :
    a,b = map(int, input().split())
    if graph[a][b] == True : # a가 b의 앞순위였다면
      graph[a][b] = False # a는 b보다 뒤 순위임
      graph[b][a] = True # b는 a보다 앞 순위임
      indegree[a] += 1 # a의 진입차수 1증가
      indegree[b] -= 1 # b의 진입차수 1감소
    else :
      graph[b][a] = False
      graph[a][b] = True
      indegree[b] += 1
      indegree[a] -= 1

  q = deque()
  for i in range(1,n+1) :
    if indegree[i] == 0 : # 진입차수가 0 인 팀을 큐에 삽입
      q.append(i)

  result = []
  certain = True # 위상 정렬 결과가 여러 개인지
  cycle = False # 사이클이 존재하는지
  for i in range(n) :
    if len(q) == 0 : # 노드가 N번 나오기 전에 큐가 빈다면 사이클이 발생 / 사이클이 있따면 그 어떤 것도 진입차수가 0 이 아니기 때문에
      cycle = True
      break
    if len(q) > 1 : # 큐에 두 개 이상의 노드가 들어가는 경우, 가능한 정렬 결과가 여러가지라는 의미
      certain = False
      break
    now = q.popleft()
    result.append(now)

    # 해당 팀보다 낮은 순위의 팀들의 진입차수에서 1 빼기
    for j in range(1, n+1) :
      if graph[now][j] == True :
        indegree[j] -= 1
      
        # 새롭게 진입차수가 0 이 되는 노드를 큐에 삽입
        if indegree[j] == 0 :
          q.append(j)

  if cycle :
    print("IMPOSSIBLE")
  elif not certain :
    print("?")
  else :
    for i in result :
      print(i, end=' ')
    print()

정해진 우선순위에 맞게 전체 팀들의 순서를 나열해야 한다 -> 위상정렬!! 이라는 생각이 떠올라야 한다.

즉, 팀 간의 순위 정보를 그래프 정보로 표현한 뒤에, 위상 정렬 알고리즘을 사용할 수 있다.

graph[a][b] = True 라면, a보다 b가 낮은 순위임을 뜻한다.

따라서 자기보다 낮은 등수를 가진 팀을 가리키도록 방향 그래프를 만들 수 있다.

 

문제의 예시처럼, 작년 순위 정보가 다음과 같다고 하자.

1등: 5팀 

2등: 4팀

3등: 3팀

4등: 2팀

5등: 1팀

이 경우, 순위 정보를 그래프로 나타내면 위와 같다.

또한, 위상정렬을 하기 위해 진입차수를 저장한 결과는 다음과 같다.

indegree[5] = 0

indegree[4] = 1

indegree[3] = 2

indegree[2] = 3

indegree[1] = 4

 

 

이를 이용해, 상대적인 등수가 바뀐 쌍이 주어졌을 때는 다음과 같이 해결할 수 있다.

if graph[a][b] == True : # a가 b의 앞순위였다면
      graph[a][b] = False # a는 b보다 뒤 순위임
      graph[b][a] = True # b는 a보다 앞 순위임
      indegree[a] += 1 # a의 진입차수 1증가
      indegree[b] -= 1 # b의 진입차수 1감소

작년에 a 가 b보다 앞순위였다면, 올해는 b가 a를 앞질렀으므로 graph 순위 정보, indegree 차수 정보를 위와 같이 갱신해야 한다.

 

 

이제 바뀐 등수를 가지고 팀들의 순서를 나열해야 한다.

처음엔 진입차수가 0 인 노드가 큐에 들어가게 된다.

우리는 "오직 하나의 경우" 의 순서가 필요한데, 이를 거스르는 경우는 다음과 같다.

• 사이클이 발생하는 경우 
  • 노드가 N번이 나오기 전에, 큐가 비게 된다면 이는 사이클이 발생했음을 알린다.
  • 사이클이 발생할 경우, 그 어떤 노드도 진입차수가 0일 수 없기 때문이다.
  • 이 경우엔 순위를 찾을 수 없으므로 "?" 를 출력한다.
• 위상 정렬의 결과가 여러 가지인 경우
  • 특정 시점에 2개 이상의 노드가 큐에 한번에 들어가는 경우, 정렬 결과가 여러가지라는 의미이다. 
  • 이 경우엔 순위가 여러가지 경우로 나올 수 있으므로 "IMPOSSIBLE" 을 출력한다.

나머지의 경우엔 위상정렬 알고리즘과 동일하다.

즉, 큐에서 pop() 한 노드보다 낮은 노드들에 대해 indegree -= 1 을 수행하고,

이때 진입차수가 0 인 노드가 다음 순위 노드로, 큐에 들어가게 된다.

큐에서 pop() 된 노드 순서대로 result 에 삽입되고, result 는 총 순위 결과값이 된다.