[백준] 3665 최종 순위 🌟

문제

• 1번 ~ N번까지의 N개의 팀 중 작년과 상대적 순위가 바뀐 팀 목록만 발표하려고 한다.
  • 작년에 팀13이 팀6보다 순위가 높았는데, 올해 팀6이 팀13보다 순위가 높다면, (6, 13)을 발표한다.
  • 2 <= N <= 500
• 작년 순위와 상대적 순위가 바뀐 M개 팀의 목록이 주어졌을 때, 올해 순위를 만들어라.
  • 0 <= M <= 25000
• 만약 확실한 순위를 찾을 수 없다면 ? 를 출력하고, 
• 데이터 일관성이 없어 순위를 정할 수 없는 경우에는 "IMPOSSIBLE" 을 출력한다.

 

풀이

• '순서' 라서 위상정렬을 떠올렸지만 어떻게 정렬할지 감을 못잡았다.
• 자신보다 순위가 낮은 팀을 가리키도록 방향 그래프를 만든 후 위상정렬을 수행해 순위를 매길 수 있다.
• 여기서, 사이클이 발생하면 IMPOSSIBLE 한 경우가 되고,
  • 일반적인 위상정렬의 경우 N개의 노드를 큐에서 출력하지만 N번이 나오기 전에 큐가 비면 사이클이 발생한 것으로 볼 수 있다.
• 위상 정렬 결과가 1개가 아니라 여러 가지가 나오는 경우는 ? 을 출력해야할 경우가 된다.
  • 큐에서 노드 뽑은 후 큐의 원소가 1개가 아니면 위상 정렬의 결과가 여러 개라고 볼 수 있다.
• => 위상 정렬 수행 과정에서 큐에서 노드를 뽑을 때 큐의 원소가 항상 1개로 유지되는 경우에만 고유 순위가 존재한다고 볼 수 있다.

 

from collections import deque

for _ in range(int(input())):   # 테스트 케이스 반복
    N = int(input())        # 팀의 수
    indegree = [0] * (N+1)  # 진입 차수
    graph = [[False]*(N+1) for _ in range(N+1)] # 방향 그래프

    # 작년 순위 입력받기
    data = list(map(int, input().split()))
    for i in range(N):
        for j in range(i+1, N):
            graph[data[i]][data[j]] = True  # i -> j  낮은 팀 가리키기
            indegree[data[j]] += 1          # 낮은 팀 진입차수 +1

    M = int(input())        # 바뀐 순위 정보 개수
    for _ in range(M):
        a, b = map(int, input().split())    # a가 b보다 낮았는데 높아졌다

        # 간선 방향 뒤집기
        # 현재 a가 b보다 높은 경우
        if graph[a][b] :
            graph[a][b] = False
            graph[b][a] = True
            indegree[a] += 1
            indegree[b] -= 1
        # 현재 a가 b보다 낮은 경우
        else:
            graph[a][b] = True
            graph[b][a] = False
            indegree[a] -= 1
            indegree[b] += 1
    
    # 위상 정렬
    result = []     # 순위 리스트
    q = deque() 

    # 진입 차수 0인 노드 큐에 삽입
    for i in range(1, N+1):
        if indegree[i] == 0:
            q.append(i)
    
    only_one = True     # 경우의 수가 하나인 경우
    cycle = False       # 사이클이 존재하는 경우

    for i in range(N):
        if len(q) == 0 :    # N번 반복 전에 큐가 비었다!
            cycle = True    # 사이클이 존재한다.
            break
    
        if len(q) >= 2:      # 큐에 2개 이상의 노드가 있다!
            only_one = False # 여러 개 경우의 수가 존재한다.
            break
        
        # 현재 노드와 연결된 노드들 진입차수 -1 
        now = q.popleft()
        result.append(now)
        for j in range(1, N+1):
            if graph[now][j] :
                indegree[j] -= 1

                if indegree[j] == 0:    # 새로 진입차수 0이 되는 노드 삽입
                    q.append(j)
    
    if cycle:
        print("IMPOSSIBLE")
    elif not only_one:
        print("?")
    else:
        print(*result)

 

References

• 이것이 코딩테스트다 Q 45
• 백준 3665번