[이코테] 그래프 알고리즘 - 최종 순위

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

3665번: 최종 순위

사고과정

• 문제에서 키워드를 잘 추출해내지 못했다.. 문제에서 캐치해야 할 것은 "작년 순위가 주어졌을 때, 이에 맞게 전체 팀들의 순위를 나열"하라는 것에서 노드의 선후관계를 고려한 위상정렬 알고리즘(그리고 위상정렬은 진입차수 테이블!)을 떠올렸어야 했다.. 그리고 주어진 작년 순위 정보를 그래프 데이터로 적절히 나타냈어야 했는데 이 부분도 해내지 못했다..
• 풀이에선 그래프 데이터로 나타내기 위해 인접리스트 방식이 아닌 인접 행렬을 선택했는데, 이는 올해의 상대적인 순위 정보가 주어졌을 때, 작년 순위에서 올해 순위로 간선 방향만 바꾸어서 업데이트해주면 되는데 이를 하기 위해서 바로 원소에 $O(1)$ 속도로 접근이 가능한 인접 행렬 방식을 선택한 듯 하다.
• 그리고 또 인상적인 점은 문제에서 "확실한 순위를 알 수 없는 경우"와 "일관성이 없는 데이터가 나올 경우"에 대해서도 처리하라고 했는데 처음에 이게 무슨 말인가.. 했는데, 위상정렬 문제라는 걸 캐치하면 위상정렬의 특이한 케이스 2가지를 생각해낼 수 있겠구나 라고 생각했다.(역시 문제에서 그냥 주어지는 조건은 없다..)
• 위상 정렬의 2가지 특이한 케이스는 사이클이 발생한 경우와 위상 정렬 결과가 2개 이상이라는 점인데, 사이클이 발생한 경우는 큐에서 원소가 N번 나오기 전에 큐에 원소가 없을 경우이고 위상 정렬 결과가 2개 이상일 때는 큐에 한번에 2개 이상의 노드가 들어갈 경우이다. 즉, 매번 큐의 길이를 계산했을 때, 길이가 2 이상이면 위상 정렬 결과가 2개 이상이라는 의미이다.(이상적인 위상정렬은 매번 큐에서 노드를 빼고 난 다음에는 원소가 1개만 존재해야 한다!)
• 정말 배울 게 많은 문제였다..계속 반복해서 풀어봐야겠다..

풀이(스스로 못 푼 풀이)

from collections import deque

for tc 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  # a 순위가 b순위보다 높다면, a -> b로 연결, b입장에서 진입차수 +1
            indegree[data[j]] += 1
    # 상대적인 등수 정보 입력
    m = int(input())
    for _ in range(m):
        a, b = map(int, input().split())  # 작년에 b가 더 높았는데 올해는 a가 더 높음! : a -> b로 바꾸기
        if graph[a][b]:  # graph[a][b] == True 라는 것은 a -> b를 의미하고 a 순위가 더 높음을 의미. 그러므로 b -> a로 바꾸어야 함
            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

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

    result = []  # 위상정렬 결과 담을 리스트
    cycle = False  # 큐에서 n번 노드가 나오기 전에 큐의 원소 길이가 0이 되었다 = 사이클 발생 = 정렬할 수 없음(순위 알 수 없음)
    certain = True  # 매번 큐 길이를 계산할 때, 큐 길이가 2이상(원소가 2개 이상)일 때, 즉 한 번에 큐에 2개 이상 원소가 들어감 = 위상 정렬 결과가 여러개!

    for i in range(n):
        if len(queue) == 0:
            cycle = True
            break
        if len(queue) >= 2:
            certain = False
            break

        # 위상 정렬 수행
        node = queue.popleft()
        result.append(node)  # 큐에서 원소를 pop하는 순서대로 결과 = 위상정렬 결과
        # 큐에서 빼낸 노드와 연결된 노드 탐색
        for j in range(1, n+1):
            if graph[node][j]:
                indegree[j] -= 1
                # 새롭게 진입차수가 0이 된 노드 큐에 넣기
                if indegree[j] == 0:
                    queue.append(j)

    if cycle:
        print('IMPOSSIBLE')
    elif not certain:
        print('?')
    else:
        for i in result:
            print(i, end=' ')
        print()