백준 3665번 - 최종순위

문제 링크

풀이과정

처음에 문제를 잘못이해해서 a,b 입력이 a보다 b가 더 상대 순위가 높다고 잘못이해했다.

t = int(input())


def topological_sort(graph, degree):
    stack = []
    arr = []
    for i in range(1, n + 1):
        if degree[i] == 0:
            stack.append(i)

    while stack:
        if len(stack) >= 2:
            print("?")
            return

        node = stack.pop()
        arr.append(node)
        for next in graph[node]:
            degree[next] -= 1
            if degree[next] == 0:
                stack.append(next)
    for i in arr:
        print(i, end=" ")


for _ in range(t):
    n = int(input())
    graph = {i: [] for i in range(1, n + 1)}
    degree = [0] * (n + 1)
    arr = list(map(int, input().split()))
    for i in range(n - 1):
        graph[arr[i]] = arr[i + 1 :]
        for j in arr[i + 1 :]:
            degree[j] += 1
    m = int(input())
    isPossible = True
    for kk in range(m):
        a, b = map(int, input().split())
        if a not in graph[b]:
            isPossible = False
            continue
        graph[b].remove(a)
        graph[a].append(b)
        degree[a] -= 1
        degree[b] += 1
    if not isPossible:
        print("IMPOSSIBLE")
        continue
    topological_sort(graph, degree)

기존 순위를 그래프로 표현한 뒤에 순위가 낮은 놈들을 모두 방향 간선으로 연결해줬다.
그리고 그 그래프와 degree를 토대로 위상정렬을 수행해서 해결했다.

t = int(input())


def topological_sort(graph, degree):
    stack = []
    arr = []
    for i in range(1, n + 1):
        if degree[i] == 0:
            stack.append(i)

    while stack:
        if len(stack) >= 2:
            print("?")
            return

        node = stack.pop()
        arr.append(node)
        for next in graph[node]:
            degree[next] -= 1
            if degree[next] == 0:
                stack.append(next)
    if len(arr) < len(degree) - 1:
        print("IMPOSSIBLE")
        return
    for i in arr:
        print(i, end=" ")


for _ in range(t):
    n = int(input())
    graph = {i: [] for i in range(1, n + 1)}
    degree = [0] * (n + 1)
    arr = list(map(int, input().split()))
    for i in range(n - 1):
        graph[arr[i]] = arr[i + 1 :]
        for j in arr[i + 1 :]:
            degree[j] += 1
    m = int(input())
    for __ in range(m):
        a, b = map(int, input().split())
        if b not in graph[a]:
            a, b = b, a
        graph[a].remove(b)
        graph[b].append(a)
        degree[b] -= 1
        degree[a] += 1
    topological_sort(graph, degree)

더 좋은 방법

더 빠른 방법들을 찾아봤다.
사실 위상정렬을 수행할 필요까지는 없엇다
어차피 한가지 결과가 나와야하고. 순위대로.. 그 순위가 겹치는 순간 잘못된 결과를 출력해야하기 때문에. 단순 degree 배열만 사용해서도 풀 수 있는 문제 였다.

# 최종 순위
from sys import stdin
input = stdin.readline

T = int(input())
def solution():
    N = int(input())
    arr = list(map(int, input().split(' ')))
    in_degree = [0] * (N+1)
    for i,v in enumerate(arr):
        in_degree[v] = i
    # original_arr = copy.deepcopy(in_degree)
    original_arr = [*in_degree]
    I = int(input())
    for _ in range(I):
        t1, t2 = map(int, input().split(' '))
        front, back = 0, 0
        if original_arr[t1] < original_arr[t2]:
            front, back = t2, t1
        else:
            front, back = t1, t2
        in_degree[front] -= 1
        in_degree[back] += 1

    result = [0] * N
    for i, v in enumerate(in_degree):
        if not result[v]:
            result[v] = i
        else:
            return print('IMPOSSIBLE')
    return print(*result, sep=" ")

for _ in range(T):
    solution()