45_최종 순위

3665번: 최종 순위

 

위상 정렬 문제다.

문제에서는 작년 순위와 상대적으로 순위가 바뀐 팀들의 목록이 주어졌을 때, 올해 순위를 만들 것을 요구한다.

즉, 정해진 우선순위에 맞게 전체 팀들의 순서를 나열해야 한다는 점에서 위상 정렬 알고리즘을 떠올릴 수 있어야 한다.

 

예를 들어 순위가

5 4 3 2 1 순으로 주어진다면

5 -> 4, 3, 2, 1

4 -> 3, 2, 1

3 -> 2, 1

2 -> 1

을 가리키도록 그래프를 만든다.

 

(여기서 이렇게 그래프를 만들었으면 바로 풀었을 텐데, 그래프를 5 -> 4 -> 3 -> 2 -> 1 이런 식으로 만들어서 풀지 못했다.)

 

그리고 큐에 진입차수가 0인 것을 집어 넣고, 반복문을 돌린다.

 

여기서 알아두어야 할 점이 있다.

위상 정렬은 2가지 특이 케이스가 발생한다.

1. 사이클 발생

2. 위상 정렬의 결과가 1개가 아니라 2개 이상인 경우

 

1. 사이클 발생

만약 반복문을 n번 돌기 전에, 큐가 비어버린다면, cycle이 발생한 것이다.  -> IMPOSSIBLE

 

2. 위상 정렬의 결과가 2개 이상인 경우

만약 반복문을 돌 때, 진입차수가 0인 노드가 2개라서 여러 위상정렬 결과가 나올 수 있는 경우, 순위가 확정되지 않은 것이다. -> ?

 

위 2가지 경우가 아닌 경우, 즉 위상 정렬 수행 과정에서 큐에서 노드를 뽑을 때 큐의 원소가 항상 1개로 유지되는 경우에만 고유한 순위가 존재한다고 볼 수 있다.

 

 

---

풀이 코드

# 3665번: 최종 순위
from collections import deque
import sys

input = sys.stdin.readline

t = int(input()) # 테스트 케이스 개수
while t:
    n = int(input()) # 팀의 수 n
    rank = list(map(int, input().split())) # 팀의 순위를 저장하는 리스트
    graph = [[False] * (n+1) for _ in range(n+1)] # 본인보다 낮은 순위들을 가리키는 리스트
    indegree = [0] * (n+1) # 진입차수를 저장하는 리스트


    for i in range(n):
        temp = rank[i+1:] # rank[i]보다 낮은 순위들 -> 가리켜야 함
        for num in temp:
            graph[rank[i]][num] = True
            indegree[num] += 1 # 진입차수 증가




    m = int(input()) # 상재거 등수가 바뀐 쌍의 수

    # 간선 방향 뒤집기
    for _ in range(m):
        a, b = map(int, input().split())

        if graph[a][b]:
            graph[a][b] = False
            indegree[b] -= 1
            graph[b][a] = True
            indegree[a] += 1
        else:
            graph[a][b] = True
            indegree[b] += 1
            graph[b][a] = False
            indegree[a] -= 1



    # 위상 정렬 시작
    queue = deque([]) # indegree가 0인 순위를 넣을 큐
    answer = [] # 올해 순위 리스트를 담을 리스트


    # 시작 노드(진입차수가 0인 노드) 큐에 넣기
    for i in range(1, n+1):
        if indegree[i] == 0:
            queue.append(i)


    # 만약 순위가 다 정해지기 전에 큐가 빈다면, cycle이 발생한 것 -> IMPOSSIBLE 출력
    # 만약 각 반복문마다 진입차수가 0인 노드가 2개 이상이라면 -> 순위가 확정되지 않은 것 -> ? 출력
    cycle = False
    certain = True
    for _ in range(n):
        # 사이클 발생
        if len(queue) == 0:
            cycle = True
            break
        
        # 확정 안됨
        elif len(queue) >= 2:
            certain = False
            break

        now = queue.popleft()
        answer.append(now)

        for i in range(1, n+1):
            if graph[now][i]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    queue.append(i)



    if cycle:
        print("IMPOSSIBLE")
    elif not certain:
        print("?")
    else:
        for num in answer:
            print(num, end=' ')
        print()

    t -= 1

 

계속 문제를 풀면서 아이디어를 생각해낼 때 2프로 부족한 느낌이 든다.

경험치의 문제인듯!