👩🏻‍💻문제설명

[이코테 Ch18-45] 최종 순위 (그래프)

✍️Idea Sketch

문제요약

팀은 1번부터 n번까지 번호가 매겨져 있다.
작년에는 최종 순위를 발표했다.
하지만 올해에는 작년과 비교하여 상대적인 순위가 바뀐 팀의 목록만 발표했다.

올해 목록을 바탕으로 올해 최종 순위를 만들어 출력해보자.

"?"를 출력 : 확실한 순위를 찾을 수 없는 경우
"IMPOSSIBLE"을 출력 : 데이터에 일관성이 없어서 순위를 정할 수 없는 경우

알고리즘 : 위상 정렬

위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다.

작년의 최종 순위는 방향성을 가지고 있다. 이를 인접 리스트로 표현한 후, 올해의 목록에 따라 일부 간선의 방향을 바꾼다. 인접 리스트를 다시 방향성에 거스르지 않도록 순서대로 나열하면 된다.

시간복잡도

O(V + E)

위상 정렬에서는 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거한다. 모든 노드와 모든 간선을 확인하므로 위상 정렬 알고리즘의 시간 복잡도는 O(V + E) 이다.

✍️내 소스코드

작년의 최종 순위를 인접리스트로 구현한다.
1 -> []
2 -> [1]
3 -> [2, 1]
4 -> [3, 2, 1]
5 -> [4, 3, 2, 1]
올해 목록을 바탕으로 간선의 방향과 진입차수를 수정한다.
위상 정렬을 구현한다.
cycle이 생긴 경우, 데이터에 일관성이 없는 것이므로 "IMPOSSIBLE"을 출력한다. 올해 목록에 (1, 2), (2, 3)이 있어 순위가 뒤집힌 경우 아래와 같이 사이클이 생긴다.
1 -> [2]
2 -> [3]
3 -> [1]
확실한 순위를 찾을 수 없다는 말은 공동 순위가 있다는 뜻이다. 하지만 올해 목록은 상대적 순위가 뒤집힌 목록일 뿐이다. 공동 2위, 공동 3위와 같은 정보는 포함하지 않는다. 따라서 작년 최종 순위에 공동 순위가 있어야 올해에도 확실한 순위를 찾을 수 없다. 애초에 작년 최종 순위에도 공동 순위는 고려하지 않으므로, "?"를 출력하는 테스트 케이스는 없다.

전체 코드

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

  t = int(si())

  for _ in range(t):
      n = int(si())
      team = list(map(int, si().rstrip().split()))

      graph = [[] for _ in range(n + 1)]
      degree = [0 for _ in range(n + 1)]

      for i in range(n - 1):
          for j in range(i + 1, n):
              graph[team[i]].append(team[j])
              degree[team[j]] += 1

      # 올해 목록
      m = int(si())
      for _ in range(m):
          a, b = map(int, si().rstrip().split())
          flag = True

          for x in graph[a]:
              if x == b:
                  graph[a].remove(b)
                  graph[b].append(a)
                  degree[b] -= 1
                  degree[a] += 1
                  flag = False

          if flag:  # a가 graph[b]에 있음
              graph[b].remove(a)
              graph[a].append(b)
              degree[a] -= 1
              degree[b] += 1

      # 위상 정렬
      queue = deque()
      answer = []

      for i in range(1, n + 1):
          if degree[i] == 0:
              queue.append(i)

      while queue:
          x = queue.popleft()
          answer.append(x)
          for y in graph[x]:
              degree[y] -= 1
              if degree[y] == 0:
                  queue.append(y)

      if len(answer) < n:
          print("IMPOSSIBLE")
      else:
          print(*answer)