1. 문제 설명

최종 순위

2. 문제 분석

위상 정렬을 통해 순위가 변경되었을 때의 정렬된 노드를 출력하는 문제다.

연결 그래프를 통해 head와 tail을 표시하고, in_degree를 통해 head의 입장에서 연결된 tail의 개수가 0일 때에만 큐에 삽입하는 건 일반적인 위상 정렬과 동일한데, 순서가 변경된 그래프가 올바르지 않은 경우가 있다. 즉 순서를 제대로 알 수 없는 상황과 불가능한 경우가 있는 것이다.

1. 순서를 제대로 알 수 없는 경우: 본 문제에서는 순서가 변경된 이후 순위가 정해져 있는데, 이는 곧 그 순간의 in-degree가 0인 노드가 하나씩만 생긴다는 것이다. 처음에 큐에 삽입할 때 그 개수가 1이 아니라면 어느 노드부터 출력해야 할지 모르는 상황이다.
2. 불가능한 경우: in-degree가 0이 되는 노드를 큐에 삽입해야 하는데, 모든 노드를 출력하기 전 이 조건을 만족하지 못해 조기 종료하는 순간이 있다. while queue를 통해 큐를 확인하고 result에 현재 노드를 넣기 때문에, 큐가 끝난 뒤 result가 모든 번호를 포함하는지 체크하자.

3. 나의 풀이

import sys
from collections import deque

t = int(sys.stdin.readline().rstrip())

for _ in range(t):
    n = int(sys.stdin.readline().rstrip())
    nodes = [[] for _ in range(n+1)]
    in_degree = [0 for _ in range(n+1)]
    rank = list(map(int, sys.stdin.readline().rstrip().split()))

    for i in range(n):
        for j in range(i+1, n):
            nodes[rank[i]].append(rank[j])
            in_degree[rank[j]] += 1

    m = int(sys.stdin.readline().rstrip())

    for _ in range(m):
        tail, head = map(int, sys.stdin.readline().rstrip().split())

        if head in nodes[tail]:
            # tail -> head를 head -> tail로 바꾼다.
            nodes[tail].remove(head)
            in_degree[head] -= 1
            nodes[head].append(tail)
            in_degree[tail] += 1
        else:
            nodes[head].remove(tail)
            in_degree[tail] -= 1
            nodes[tail].append(head)
            in_degree[head] += 1

    queue = deque()

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

    if len(queue) > 1: print('?')
    # 처음 시작하는 노드를 알지 못할 때 ? 출력
    else:
        result = []
        while queue:
            cur_node = queue.popleft()
            result.append(cur_node)

            for next_node in nodes[cur_node]:
                in_degree[next_node] -= 1
                if in_degree[next_node] == 0:
                    queue.append(next_node)

        if len(result) == n: print(*result, sep=' ')
        # 변경된 순위를 정상적으로 출력
        else: print('IMPOSSIBLE')
        # 큐에서 꺼낼 다음 노드가 없어서 도중 종료되었을 때