[그래프 이론] 최종순위

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 40분 + a

1. 문제 설명

- 테스트 케이스의 개수가 주어진다.
    - 각 테스트 케이스별로 팀 수, 작년에 i등을 한 팀의 번호
    - 상대적인 등수가 바뀐 쌍의 수가 입력으로 주어진다. 

- 출력형식은 다음과 같다.
- 1등팀부터 순서대로 출력한다. 
- 확실한 순위를 찾을 수 없다면 ?를 출력한다.
- 데이터에 일관성이 없어서 순위를 정할 수 없는 겨우 'IMPOSSIBLE'을 출력한다.

2. 접근 방식

- 위상정렬 알고리즘을 활용한다.
- 순위를 진입차수로 구분한다. 진입차수가 큰 것일 수록 순위가 낮다는 것으로 생각한다.
- 확실한 순위를 찾을 수 없는 경우나, 데이터에 일관성이 없는 경우는 cycle이 발생하거나, 여러가지 경우가 나올 수 있는 경우로 구분해서 표시한다. 매 반복마다 이를 체크한다.

3. 코드

from collections import deque


for _ in range(int(input())):
    n = int(input())
    teams = list(map(int, input().split()))
    
    # 1) 위상정렬을 위한 초기 변수 설정
    graph = [[False]*(n+1) for _ in range(n+1)]
    indegree = [0]*(n+1)
    
    # 2) 순위별로 진입차수 설정 및 그래프 방향 설정(True가 많을 수록 순위가 높다고 생각)
    for a in range(n):
        for b in range(a+1, n):
            graph[teams[a]][teams[b]] = True
            indegree[teams[b]] += 1

    # 3) 등수가 바뀐 팀의 그래프 방향과 진입차수 수정
    m = int(input())
    for _ in range(m):
        a, b = map(int, input().split())
        if graph[a][b]:
            graph[a][b] = False
            graph[b][a] = True
            indegree[a] += 1
            indegree[b] -= 1            
        else:
            graph[a][b] = True
            graph[b][a] = False
            indegree[b] += 1
            indegree[a] -= 1
            
    # 4) 결과 출력을 위한 변수 설정
    q = deque()
    cycle = False
    consist = True
    result = []
    
    # 5) deque리스트 초기화
    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)
            
    # 6) 위상정렬 수행
    for i in range(n):
        # 6-1) for문이 끝나기 전에 deque가 빈다면 cycle발생
        if len(q) == 0:
            cycle=True
            break
        # 6-2) 진입차수가 동일한 것이 2개가 deque에 들어왔다면, 다양한 경우의 수가 존재할 가능성 발생
        if len(q) >= 2:
            consist = False
            break
        now = q.popleft()
        result.append(now)
        for j in range(1, n+1):
            if graph[now][j]:
                indegree[j] -= 1
                if indegree[j] == 0:
                    q.append(j)
                    
    # 7) 코드 수행 결과에 따른 출력 진행
    if cycle:
        print("IMPOSSIBLE")
    elif not consist:
        print("?")
    else:
        for answer in result:
            print(answer, end = " ")
        print()

4. 코멘트

- 문제를 처음에는 여러 그래프 이론을 생각해봤는데, 위상정렬로 풀어야겠다는 생각을 했었다. 하지만 순위를 어떻게 설정할 것인지에 대해 고민을 하다가 결국 해답을 보게 됐다. 1등의 경우 진입차수를 0으로 주고, 순위가 낮을 수록 진입차수를 더해가면서 깊게 만드는 방법을 사용하고 있었다. 그리고 방향 그래프를 같이 사용하면서 '상대 순위'가 바뀌었을 때에도 처리하는 것을 보고 꽤나 신박하다는 생각을 했다. 그리고 답이 없는 경우나 무결성 등을 지키기 위한 것을 CYCLE이나 DEQUE의 원소들을 계산하는 기법들은 생각하지 못했을 거 같다.

- 여러모로 이번 문제는 별 3개짜리 문제답게 어려웠었던 것 같다. 그리고 한 편으로는 다양한 기법들을 배울 수 있었던 것 같다. 다시 여러번 풀어보면서 체화시키는 연습을 해야겠다.