[BOJ/백준] 3665 최종 순위

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())


for tc in range(T):
    N = int(input())
    graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
    # 전년도 1등부터 ~ N등까지 팀 순서
    prev_order_team = list(map(int,input().split()))
    indegree = [0]*(N+1)
    indegree[0] = float('inf')
    for rank,team_num in enumerate(prev_order_team):
        indegree[team_num] = rank
        for low_team_num in prev_order_team[rank+1:]:
            graph[team_num][low_team_num] = 1

    M = int(input())
    new_indegree = indegree[:]
    for _ in range(M):
        a_team,b_team = map(int,input().split())
        if indegree[a_team] > indegree[b_team]:
            a_team,b_team = b_team,a_team

        # a_team이 상위권 b_team이 하위권 원래는
        graph[b_team][a_team] = 1
        graph[a_team][b_team] = 0
        new_indegree[a_team] += 1
        new_indegree[b_team] -= 1
    indegree = new_indegree[:]
    stack = deque()

    for team_num in range(1,N+1):
        if not indegree[team_num]:
            stack.append(team_num)
    result = []
    if len(stack) == 1:
        cnt = 0
        while cnt<N:
            if not len(stack):
                result = 'IMPOSSIBLE'
                break
            elif len(stack) > 1:
                result = '?'
                break

            cur_node = stack.popleft()
            result.append(cur_node)
            for next_node in range(1,N+1):
                if graph[cur_node][next_node]:
                    indegree[next_node] -= 1
                    if not indegree[next_node]:
                        stack.append(next_node)
            cnt += 1
    elif len(stack) == 0:
        result = 'IMPOSSIBLE'
    else:
        result = '?'
    if type(result) == list:
        print(*result)
    else:
        print(result)

 

 

이 문제는 최근에 풀었던 문제 중에서 문제를 이해하는데 가장 힘들었던 문제였다. 문제를 이해하고 보면,

 

쉽게 이해가 가능한 문제이다.

 

문제에 주어진 N개의 숫자는

 

앞에서부터 1등부터 N등까지를 표현한 것이다.

 

그리고 그 각 자리에 있는것이 1등을 한 팀 N_1  2등을 한 팀 N_2 이런식인것이다.

 

그러면 문제에 첫 예제로 주어진

 

5 4 3 2 1

 

1등은 5팀

2등은 4팀

3등은 3팀

4등은 2팀

5등은 1팀

 

이 된것이다. 그렇다는 것은 이걸 그래프적으로 표현을 하면 다음과 같다.

 

 다음 과 같이 표현을 할 수 있을 것이다.

 

5팀이 가장 루트 노드이고, 이 5팀을 지나가고 난뒤에 4팀 3팀 2팀 1팀을 순서적으로 할 수 있는것이다.

 

그러면 여기서 상대적인 등수가 바뀌었다는 것은

 

저 그래프에서의 순서가 뒤바뀐다는 것을 의미하게 된다.

 

그러면 첫번째 예제에선

 

2 4

3 4 라는 입력이 주어졌다.

 

그러면

 

빨갛게 동그라미 모양이 된 화살표가 반대로 가게 되는것이다.

 

 

 

즉 녹색화살표 처럼 반대로 표시가 바뀌게 된것이다.

 

그러면 이때의 순위는

 

5 -> 3->2->4->1 순서가 되는 것을 알 수 있다.

 

그래서 이 문제에서 중요한 것은

 

처음 입력이 주어졌을때 자기 등수보다 이하의 등수들에게 부모 자식 관계를 나타내느 그래프 간선을 그려준다.

 

 

그리고 난뒤에 m개의 상대적인 순위가 바뀌었다는 입력이 들어오면

 

서로원래의 rank를 확인해서

 

높은 랭크 -> 낮은 랭크로 연결되어있던 간선을 반대로 바꾸어주고,

 

우리가 간선을 들어온 개수를 세어놓은 indegree 수치를

 

낮은 순위는 1개를 줄여주고, 높은 순위는 1개를 높여주면 된다.

 

그리고 여기서 주의해야할 것은 바로 값을 바꾸면 바뀐 순위를 참조가 가능하므로,

 

복사된 배열에서 값을 변경시키고 나중에 옮겨줘야한다.

 

그리고 정상적인 위상정렬을 시행해주면 된다.

 

만약에 스택이 비게되면 사이클이 발생한 것이므로,  impossible을

 

스택에 길이가 2개이상이 된다는것은 같은 rank에 2개가 있게 되는 것이므로, ?를 출력하게 해주면 된다.

 

 

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())

    prev_rank = [0]*(N+1)
    current_rank = [0]*(N+1)
    arr = list(map(int,input().split()))
    for i in range(N):
        prev_rank[arr[i]] = i +1
        current_rank[arr[i]] = i + 1

    M = int(input())

    for _ in range(M):
        a_team,b_team = map(int,input().split())

        if prev_rank[a_team] > prev_rank[b_team]:
            current_rank[a_team] -= 1
            current_rank[b_team] += 1
        else:
            current_rank[a_team] += 1
            current_rank[b_team] -= 1

    result = [0]*(N+1)
    flag= False
    for team_num in range(1,N+1):
        if result[current_rank[team_num]]:
            flag = True
            break
        else:
            result[current_rank[team_num]] = team_num

    if flag:
        print('IMPOSSIBLE')
    else:
        print(*result[1:])

 이건 좀 더 간단한 풀이이다.

 

 하지만 이 풀이는 ?인 경우가 없다고 가정하고 푼 것이다.