[Graph] 이코테 “최종 순위” Python 풀이

문제

• 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했습니다.
• 팀은 1번부터 n번까지 번호가 매겨져 있습니다.
• 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일합니다.
• 올해 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했습니다.
• 그 대신에 작년에 비해서 상대적으로 순위가 바뀐 팀의 목록만 발표하려고 합니다. (작년에는 순위를 발표했습니다.)
• 예를 들어, 작년에 팀13이 팀6보다 순위가 높았는데, 올해 팀6이 팀13보다 순위가 높다면, (6, 13)을 발표할 것입니다.
• 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 합니다.
• 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하세요.
• 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있습니다.
• 이 두 경우도 모두 찾아내야 합니다.

입력 조건

• 첫째 줄에는 테스트 케이스의 개수가 주어집니다. 테스트 케이스는 100개를 넘지 않습니다.
• 각 테스트 케이스는 다음과 같이 이루어져 있습니다.
  • 팀의 수 n을 포함하고 있는 한 줄. (2 <= n <= 500)
  • n개의 정수 ti를 포함하고 있는 한 줄. (1 <= ti <= n)
    • ti는 작년에 i등을 한 팀의 번호입니다.
    • 1등이 가장 성적이 높은 팀입니다.
    • 모든 ti는 서로 다릅니다.
  • 상대적인 등수가 바뀐 쌍의 수 m. (0 <= m <= 25000)
  • 두 정수 ai와 b를 포함하고 있는 m 줄. (1 <= ai < bi <= n)
    • 상대적인 등수가 바뀐 두 팀이 주어집니다.
    • 같은 쌍이 여러 번 발표되는 경우는 없습니다.

출력 조건

• 각 테스트 케이스에 대해서 다음을 출력합니다.
  • n개의 정수를 한 줄에 출력합니다.
  • 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력합니다.
  • 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력합니다.
  • 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력합니다.

입력 예시

3
5
5 4 3 2 1
2
2 4
3 4
3
2 3 1
0
4
1 2 3 4
3
1 2
3 4
2 3

출력 예시

5 3 2 4 1
2 3 1
IMPOSSIBLE

풀이

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

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

• 다시 말해 이 문제는 팀 간의 순위 정보를 그래프 정보로 표현한 뒤에, 위상 정렬 알고리즘을 이용해 해결할 수 있다.

• 문제에 제시된 예시 중 하나를 가지고 생각해보자

    # 작년 순위 정보
    1등 : 팀 5
    2등 : 팀 4
    3등 : 팀 3
    4등 : 팀 2
    5등 : 팀 1

• 위와 같은 작년의 순위 정보가 주어지면, ‘자기보다 낮은 등수를 가진 팀을 가리키도록’ 방향 그래프를 만들 수 있다.

• 만약에 이대로 위상 정렬을 수행하게 되면, 수행 결과는 5 - 4 - 3 - 2 - 1 이 된다.

• 즉, 문제에서 제시한 순위 정보와 동일하게 나온다.

• 다른 경우는 존재하지 않는다.

• 이제 상대적인 순위가 바뀌게 되는 경우에는, 해당 간선의 방향을 반대로 변경하면 된다.

• 이후에 이 상태에서 위상 정렬을 다시 수행하면 된다.

• 위상 정렬은 2가지 특이 케이스가 존재한다.

  1. 사이클이 발생하는 경우
  2. 위상 정렬의 결과가 1개가 아니라 여러 가지인 경우

• 이 2가지 경우에 해당하지 않는다면 위상 정렬을 수행한 결과는 ‘오직 하나의 경우’만 존재하게 된다.

• 즉, 가능한 순위가 하나라는 의미가 된다.

• 따라서 변경된 상대적인 순위를 적용한 이후에, 위상 정렬 알고리즘을 실행하면서 사이클이 발생하는지, 혹은 결과가 여러 가지인지 확인하면 된다.

• 일반적인 위상 정렬의 경우, 정확히 N개의 노드가 큐에서 출력이 된다.

• 만약 노드가 N번 나오기 전에 큐가 비게 된다면, 사이클이 발생한 것으로 이해할 수 있다.

• 또한 특정 시점에 2개 이상의 노드가 큐에 한꺼번에 들어갈 때는, 가능한 정렬 결과가 여러 가지라는 의미가 된다.

• 그러므로 위상 정렬 수행 과정에서 큐에서 노드를 뽑을 때 큐의 원소가 항상 1개로 유지되는 경우에만 고유한 순위가 존재하는 것으로 이해할 수 있다.

• 그러므로 위상 정렬 소스코드에서 매 시점마다 큐의 원소가 0개이거나, 2개 이상인지를 체크하는 부분을 넣어주어 정답 소스코드를 작성할 수 있다.

• 알고리즘에 대한 세부 설명은 아래 예제 코드와 같다.

예제 코드

# https://www.acmicpc.net/problem/3665

import sys
from collections import deque

# 테스트 케이스의 개수 
tc = int(sys.stdin.readline())

for _ in range(tc):

    # 팀의 수 n
    n = int(sys.stdin.readline())

    # 각 노드의 진입차수 초기화
    indegree = [0] * (n+1)

    # 각 노드에 연결된 간선 정보를 담기 위한 인접 행렬 초기화
    # [큰 순위의 팀 번호][작은 순위의 팀번호] = True
    graph = [[False] * (n + 1) for i in range(n + 1)]

    # 작년 팀 등수 (인덱스 == 등수, 값 == 팀 번호)
    t = list(map(int, sys.stdin.readline().split()))

    # 방향 그래프의 간선 정보 초기화
    for i in range(n):
        for j in range(i + 1, n):
            # [큰 순위의 팀 번호][작은 순위의 팀번호] = True
            graph[t[i]][t[j]] = True
            # 진입 차수 추가
            indegree[t[j]] += 1

    # 올해 변경된 순위 정보 입력
    m = int(sys.stdin.readline())
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())

        # a, b가 큰 순위의 팀번호, 작은 순위의 팀 번호라면
        if (graph[a][b]):
            graph[a][b] = False
            graph[b][a] = True
            indegree[b] -= 1
            indegree[a] += 1
        # 반대라면
        else:
            graph[b][a] = False
            graph[a][b] = True
            indegree[a] -= 1
            indegree[b] += 1

    # 위상 정렬(Topology Sort) 시작
    result = [] # 알고리즘 수행 결과를 담을 리스트
    q = deque() # 큐 기능을 위한 deque 라이브러리 사용

    # 진입 차수가 0인 노드를 찾아 큐에 삽입
    for i in range(1, n+1):
        if (indegree[i] == 0):
            # 큐에 팀 번호 삽입
            q.append(i)

    cycle = False # 데이터에 일관성이 없어서 순위를 정할 수 없는 경우 == 사이클이 발생하는 경우 == 노드가 N번 나오기 전에 큐가 비게 되는 경우
    certain = True # 확실한 순위를 찾을 수 없는 경우 == 특정 시점에 2개 이상의 노드가 큐에 한꺼번에 들어가는 경우

    # 정확히 노드의 개수만큼 반복
    for i in range(n):
        # 큐가 비어 있다면 사이클이 발생했다는 의미
        if len(q) == 0:
            cycle = True
            break
        # 큐의 원소가 2개 이상이라면 가능한 정렬 결과가 여러 개라는 의미
        if len(q) >= 2:
            certain = False
            break
        # 큐에서 원소 꺼내기
        now = q.popleft()
        # 결과 리스트에 추가
        result.append(now)

        # 해당 노드와 연결된 노드들의 진입 차수 빼기
        for j in range(1, n+1):
            if (graph[now][j] == True):
                indegree[j] -= 1
                # 새롭게 진입 차수가 0이 된 노드를 찾아 큐에 삽입
                if (indegree[j] == 0):
                    q.append(j)

    # 사이클이 발생하는 경우(일관성이 없는 경우)
    if cycle == True:
        print("IMPOSSIBLE")
    # 위상 정렬 결과가 여러 개인 경우
    elif certain == False:
        print("?")
    # 위상 정렬을 수행한 결과 출력
    else:
        for i in result:
            print(i, end=' ')
        print()

참고

• 이것이 취업을 위한 코딩 테스트다. with python