[백준] 최종 순위

출처:: www.acmicpc.net/problem/3665

분류:: 위상정렬 

 

1. 문제 이해 및 해결과정

- 정해진 순위에 맞게 팀들의 순서를 나열해야한다 -> 위상정렬 - 순위정보가 주어지면, 자기보다 낮은 등수를 가진 팀을 가리키도록 방향그래프를 만든다 - 상대적 순위가 바뀌면 간선의 방향을 반대로 바꾼다 - 위상정렬을 다시 수행하면 특이 케이스가 발생할 수 있다 -  1) 사이클이 발생하는 경우(IMPOSSIBLE)     2) 위상정렬의 결과가 1개가 아니라 여러가지인 경우(?) - 일반적인 위상정렬은 N개의 노드가 출력   노드가 N번 나오기 전에 큐가 비게 되면 ? 1번의 경우이다 => 큐의 원소가 0개   특정시점에 2개 이상의 노드가 큐에 한꺼번에 들어가면? => 정렬결과가 여러가지 => 큐의 원소가 2개 이상

 

2. 풀이방법

 1. python

#최종순위
#https://www.acmicpc.net/problem/3665
import sys
from collections import deque
sys.stdin = open("input.txt","r")

for t in range(int(input())): #테스트케이스 수만큼
    n=int(input()) #노드의 수
    indegree=[0]*(n+1)
    graph=[[False]*(n+1) for _ in range(n+1)]
    rank=list(map(int,input().split()))

    #그래프그리기
    for i in range(n):
        for j in range(i+1,n):
            graph[rank[i]][rank[j]]=True
            indegree[rank[j]]+=1

    m=int(input())#바뀌는 순위
    for i 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[a] -= 1
            indegree[b] += 1

    cycle=False #사이클이 없다
    flag=True #하나만 있을 경우, 일관성이 없는 정보
    result=[]
    q=deque()

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

    #노드의 개수만큼 반복
    for i in range(n): #빈경우를 생각해서 while q 안씀 
        if len(q)==0: #사이클이 있을 경우
            cycle=True
            break
        if len(q)>=2: #위상정렬 여러개
            flag=False
            break
        cur = q.popleft()
        result.append(cur)
        for i in range(1,n+1): #노드와 연결된 노드들의 진입차수에서 1빼기
            if graph[cur][i]:
                indegree[i]-=1
                if indegree[i]==0:
                    q.append(i)

    if cycle: #사이클이 발생하면
        print("IMPOSSIBLE")
    elif not flag: #일관성이 없으면, 여러 위상정렬의 경우가 나오면
        print("?")
    else:
        for x in result:
            print(x,end=' ')
        print()

 

3. 오답원인

 

4. 알게된 점