[백준] 1365번 최종 순위 (Python)

백준 1365 최종 순위

위상정렬을 활용한 문제임은 금방 알 수 있었지만, 구현하는 과정에서 삽질을 좀 많이 했다. 해당 문제에서 포인트는 "순위가 바뀐 모든 팀의 목록이 주어졌을 때"라는 조건이다.

1 -> 2 -> 3 이라는 순서로 주어진다고 가정하면 3의 선행 조건은 2가 아닌 1, 2 모두이다.

순위가 바뀐 팀들의 선행 갯수와 자식 노드를 변경해준다. 또한, 자식 노드인지 확인할 때 시간을 단축하기 위해서 set을 활용한다. 또한 시작점도 set을 활용해 저장하고 입력을 모두 받은 후에는 filter()를 활용해 선행 갯수가 0개인 노드를 저장한다.

1. 시작 노드가 2개 이상인 경우는 우선순위가 정해지지 않으므로 "?"
2. 시작 노드가 없는 경우는 시작할 수 없으므로 "Impossible"
3. 자식 노드 중에 2개 이상의 노드가 indegree가 0이라면 우선 순위를 정할 수 없으므로 "?"
4. 방문한 노드를 또 방문한다면 순위가 순환되므로 "Impossible"

import sys
from collections import deque

input = sys.stdin.readline
qr = int(input().strip())
for __ in range(qr):
    n = int(input().strip())
    childs = [set() for _ in range(n + 1)]   # 자식을 저장할 리스트
    indegree = [-1 for _ in range(n + 1)]   # 선행 갯수
    starts = set()              # 시작점을 저장할 집합
    res = []                    # 결과를 저장할 배열
    l = list(map(int, input().split()))
    starts.add(l[0])

    # 자식, 선행 갯수 업데이트
    for i in range(len(l)):
        childs[l[i]] = set(l[i + 1:])
        indegree[l[i]] = i
    # 바뀐 자식, 선행 갯수 업데이트
    for _ in range(int(input().strip())):
        a, b = map(int, input().split())
        if a in childs[b]:
            a, b = b, a
        childs[a].remove(b)
        indegree[a] += 1
        childs[b].add(a)
        indegree[b] -= 1
        if indegree[a] == 0:
            starts.add(a)
        if indegree[b] == 0:
            starts.add(b)

    start = list(filter(lambda x: indegree[x] == 0, starts))
    # 시작 점이 없다면 불가능
    if len(start) == 0:
        print("IMPOSSIBLE")
        continue
    # 시작 점이 여러개라면 순서 지정 불가능
    elif len(start) > 1:
        print("?")
        continue

    dq = deque()
    dq.append(start[0])
    isVisit = [False for _ in range(len(l) + 1)]
    isBreak = False
    isVisit[start[0]] = True
    while dq:
        n = dq.popleft()
        res.append(n)
        isFound = False
        for child in childs[n]:
            # 방문한 적이 있다면 순서가 존재할 수 없음
            if isVisit[child]:
                print("IMPOSSIBLE")
                isBreak = True
                break
            indegree[child] -= 1
            if indegree[child] == 0:
                if not isFound:
                    isFound = True
                    isVisit[child] = True
                    dq.append(child)
                # 같은 순서에 두 개 이상의 child가 발생하면 순서를 지정할 수 없음
                else:
                    print("?")
                    isBreak = True
                    break
            # print(indegree)
    if not isBreak:
        if len(res) == len(l):
            print(*res)
        else:
            # 순서 연결이 끊겼다면 순서를 정할 수 없음
            print("IMPOSSIBLE")