백준 3665 최종순위 문제풀이

문제 

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

3665번: 최종 순위

 

 

문제 접근 방식

전년도 팀들의 순위가 주어지고, 올해 관계가 바뀐 팀들만 주어진다. 두 팀간의 의존성이 주어지기 때문에 위상정렬 문제로 판단했다. 바뀐 팀들만 부분적으로 의존성이 주어지기 때문에 전년도 순위를 어떻게 활용할 것인지가 문제였다.

 

전년도 팀 순위도 위상정렬을 사용하기 위해 변형할 필요가 있었고 아래 그림처럼 이웃한 노드 뿐 아니라 떨어져 있는 노드간의 관계도 인접리스트와 진입차수로 표현하였다.

 

위와 같은 방식으로 전년도 각 팀간의 관계 및 진입차수를 구해놓고, 올해 변경사항에 대해 인접리스트 관계 및 진입차수를 반대로 변경을 해놓고 위상정렬을 하였다.

 

 

정답을 출력하는 부분에서 정상적으로 위상 정렬을 수행하는 것 외의 경우의 수가 존재한다. 

첫번째로는, 노드간 순서가 확실하지 않은 경우이다. 아래와 같이 그림의 상태이며, 이런 경우 큐에 노드가 여러 개 들어가게 된다. 큐에 2개 이상의 노드가 들어가 있을 때 '?' 을 출력하면 된다.

 

두번째로는, 데이터의 일관성이 없는 경우이다. 올해 바뀐 팀들의 정보를 토대로 변경을 했으나 말이 안되는 경우가 발생한다는 것인데 이런 상황은 아래 그림과 같다. 이렇게 되는 경우 어느 순간 진입차수가 0인 노드가 없게 된다. 큐를 순회한 이후, 정답의 노드 개수가 전체 노드 개수와 일치하지 않고, 첫번째 경우에 해당하지 않을 때 'IMPOSSIBLE' 을 출력하면 된다.

 

시간 복잡도

이전 팀의 순위를 위상정렬로 변형하는 과정에서 O(N^2),  변경 사항 입력 부분에서 O(M), 위상 정렬에서 O(N+E) = O(N+N^2) = O(N^2) 이 걸린다. 전체적인 시간복잡도는 O(N^2 + M) 이고, N의 최댓값은 500, M의 최댓값은 25000 이므로 시간 내에 동작한다.

 

 

코드

import sys
input=sys.stdin.readline
print=sys.stdout.write
if __name__=='__main__':
    t=int(input())
    for _ in range(t):
        n=int(input())
        ranking=list(map(int,input().split()))

        # 작년 순위에 대한 간선 정보를 입력 후, m 개의 변경 사항을 반영할 예정
        adj=[[] for _ in range(n+1)]
        in_degree=[0]*(n+1)

        for i in range(n):
            for j in range(i+1,n):
                a,b=ranking[i],ranking[j]
                adj[a].append(b)
                in_degree[b]+=1

        # 변경된 랭킹을 입력받고, 인접리스트와 진입차수를 갱신한다.
        m=int(input())
        for __ in range(m):
            a,b=map(int,input().split())

            # a -> b 였던 것으로 가정
            # 주어진 정보가 b -> a 라면, a와 b를 swap
            if b not in adj[a]:
                a,b=b,a

            # 인접 리스트와 진입차수의 관계를 반대로 변경
            adj[a].remove(b)
            adj[b].append(a)
            in_degree[b]-=1
            in_degree[a]+=1


        # 위상 정렬 진행
        answer=[]
        ordered=True #순서가 확실한 것인지를 저장

        # 큐에 진입차수 0 인것을 삽입
        q=[]
        for i in range(1,n+1):
            if in_degree[i]==0:
                q.append(i)

        while q:
            if len(q)>=2: # 큐에 진입차수가 0 인 것이 2개 이상이라면 순서가 확실하지 않은 것 존재
                ordered=False
                break

            now=q.pop(0)
            answer.append(str(now))

            for next in adj[now]:
                in_degree[next]-=1
                if in_degree[next]==0:
                    q.append(next)

        if len(answer)==n: # 모든 노드를 방문했다면 정답 출력
            print(' '.join(answer)+'\n')
        elif not ordered: # 순서가 확실하지 않다면 '?' 출력
            print('?\n')
        else: # 진입차수가 0 인 것이 존재하지 않아서 중간에 멈춘 경우 'IMPOSSIBLE' 출력
            print('IMPOSSIBLE\n')

 

 

회고

배운점

1. 순서대로 나열된 리스트를 위상정렬로 변형할 수 있다.
2. 위상정렬이 불가능한 상황과, 순서가 확실하지 않는 상황이 존재한다.
3. 위상정렬을 활용하여 그래프상 사이클의 존재를 판단할 수 있다.