[Baekjoon Online Judge] 백준 3665번 최종 순위(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 3665번 최종 순위

(Python)

(글쓴날 : 2020.06.17)

 

---

* Baekjoon Online Judge, 백준 3665번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 3665번 최종 순위

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/3665

3665번: 최종 순위

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

작년도 ACM-ICPC 대회 팀들의 순위가 주어지고, 올해 순위가 바뀐 모든 팀들의 목록이 주어질 때, 올해 최종 순위를 구하는 문제입니다.

 

저의 경우, 위상 정렬을 적용하였고, Python을 사용했습니다.

우선, 작년도 순위를 인접 리스트로 구현한 뒤, 올해 바뀐 순위를 인접 리스트에서 찾아내 갱신한 후, 위상 정렬을 적용하여 문제를 해결했습니다.

주의해야 할 점은 올해 바뀐 순위가 일관성이 없는 잘못된 정보일 수도 있으므로, 그래프에 사이클이 생겨 위상 정렬 수행 중 큐가 빈 상태가 될 경우에 대비해 "IMPOSSIBLE"을 출력할 수 있도록 예외 처리를 해야 합니다.

추가로, 만약 확실한 순위를 찾을 수 없다면 "?"를 출력하라고는 하지만, 문제에서 순위가 바뀐 모든 팀들의 목록을 제공하므로 해당 경우가 발생할 일은 없습니다.

구현 자체는 위상 정렬 수행 도중 큐의 길이가 1을 초과하는지 확인하는 예외 처리를 하면 됩니다.

만약, 큐 안에 2개 이상의 팀이 있을 시, 해당 팀들은 같은 위상이므로 확실한 순위를 찾을 수 없게 됩니다.

---

3) 코드

 

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
 
def topologicalSort():
    global isImpossible, isAmbiguous
 
    for _ in range(n):
        if not dq:
            isImpossible = True
            return
        if len(dq) > 1:
            isAmbiguous = True
            return
 
        target = dq.popleft()
        sequence.append(target)
 
        for x in adjList[target]:
            indegree[x] -= 1
 
            if not indegree[x]:
                dq.append(x)
 
 
T = int(input())
 
for _ in range(T):
    n = int(input())
 
    isImpossible = False
    isAmbiguous = False
    sequence = []
    indegree = [0] * (n + 1)
    adjList = [[] for _ in range(n + 1)]
 
    lastYear = list(map(int, input().split()))
    
    for i in range(0, n):
        for j in range(i + 1, n):
            indegree[lastYear[j]] += 1
            adjList[lastYear[i]].append(lastYear[j])
 
    m = int(input())
    for _ in range(m):
        a, b = map(int, input().split())
 
        isNotFound = True
 
        for x in adjList[a]:
            if x == b:
                isNotFound = False
                indegree[b] -= 1
                indegree[a] += 1
                adjList[a].remove(b)
                adjList[b].append(a)
        
        if isNotFound:
            indegree[a] -= 1
            indegree[b] += 1
            adjList[b].remove(a)
            adjList[a].append(b)
 
    dq = deque()    
    for i in range(1, n + 1):
        if not indegree[i]:
            dq.append(i)
    
    topologicalSort()
    
    if isImpossible:
        print("IMPOSSIBLE")
    elif isAmbiguous:
        print("?")
    else:
        print(*sequence)

---