[BOJ] Q3665 최종 순위

[BOJ] Q3665 최종 순위

Question

Language: Python

Difficulty: Gold 1

작년의 종합 순위를 알려주고, 올해에는 변화된 순위 정보만을 제공했을 때, 이를 토대로 올해의 종합순위를 알 수 있는 가에 대한 문제 –> Graph에서 순위? Topological Sorting이다.

우선, 그래프를 생성해줘야 하는데, 순위가 낮은 팀에서 높은 팀으로 이어주는 방식으로 그래프를 생성해준다.

올해에 순위가 바뀐 팀에 대한 정보를 이용해서 그래프를 수정한 다음 이를 Topological Sorting을 진행해본다.

Solution

from collections import deque
def solution():
    queue=deque()
    confused=False
    cycle=False
    sorted_list=[]
    

    for i in range(1,n_teams+1):
        if indegree[i]==0:
            queue.append(i)
 
    for _ in range(n_teams):
        if len(queue)==0:
            cycle=True
            break

        if len(queue)>=2:
            confused=True
            break

        vertex=queue.popleft()
        sorted_list.append(vertex)
        for adj_vertex in range(1,n_teams+1):
            if graph[vertex][adj_vertex]:
                indegree[adj_vertex]-=1

                if indegree[adj_vertex]==0:
                    queue.append(adj_vertex)

    if cycle or confused:
        print("IMPOSSIBLE")
    else:
        print(*sorted_list)
        

if __name__ =="__main__":
    testcases=int(input())
    for _ in range(testcases):
        n_teams=int(input())
        graph=[[False] * (n_teams+1) for _ in range(n_teams+1)]
        indegree=[0]*(n_teams+1)          
        teams=list(map(int,input().split()))
        for i in range(n_teams):
            for j in range(i+1,n_teams):
                indegree[teams[j]]+=1
                graph[teams[i]][teams[j]]=True
            
        n_changes=int(input())
        for _ in range(n_changes):
            v1,v2=map(int,input().split())
            if graph[v1][v2]:
                indegree[v2]-=1
                indegree[v1]+=1
                graph[v1][v2]=False
                graph[v2][v1]=True
                
            else:
                indegree[v1]-=1
                indegree[v2]+=1
                graph[v2][v1]=False
                graph[v1][v2]=True
        solution()