백준 3665번 문제이다
정해진 순위에 맞추어 팀들을 출력해야한다는 문제를 보고 위상정렬을 생각했다. 위상 정렬이란 비순환 그래프의 모든 노드들을 방향성에 맞게 순서대로 나열하는 정렬으로 큐 구조를 이용하여서 노드의 in*degree(진입 차수)가 0인 노드들을 거쳐가며 정렬을 하면 된다.
이 문제에서는 순위가 낮은(1등이 제일 낮다) 노드에서 큰 노드로 진입 차수를 그려주고, 순위가 바뀐 팀들이 입력되면 경로의 방향을 반대로 하여 위상 정렬을 하면 된다.
다만 순위를 찾을 수 없거나, 일관되지 않은 경우도 고려를 해준다. 큐에서 사이클이 돌면 일관되지 않았다고 생각할 수 있고, 큐에는 하나의 노드만 들어가 있어야하는데 만약 그렇지 않다면 순위를 정확히 알 수 없는 것이다.
코드는 다음과 같다.
from collections import deque
tc = int(input())
for* in range(tc): # 입력된 수만큼 반복
n = int(input())
indegree = [0] *(n + 1) #각 노드의 진입차수
data = list(map(int, input().split())) #작년 순위 입력
graph = [[False]* (n + 1) for \_ in range(n + 1)] #각 노드 끼리 방향 초기화
for i in range(n - 1):
for j in range(i + 1, n): # 순위가 뒤쳐진 노드를 거치며 graph를 true로 설정
graph[data[i]][data[j]] = True
indegree[data[j]] += 1
change = int(input())
for i in range(change):
a, b = map(int, input().split())
if graph[a][b] == True:
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
q = deque()
result = []
for i in range(1, n + 1):
if indegree[i] == 0: #진입차수가 0이면 큐에 추가
q.append(i)
certain = True #한가지의 경우인 지 판단
cycle = False #일관된 결과인지 판단
for i in range(n):
if len(q) == 0: #큐가 비면 사이클이 돌았다는 의미
cycle = True
break
if len(q) > 1: #큐에 두가지 이상 노드가 있으면 확실한 순위가 없다는 의미
certain = False
break
now = q.popleft()
result.append(now)
for j in range(1, len(graph[now])):
if graph[now][j] == True:
indegree[j] -= 1
if indegree[j] == 0:
q.append(j)
if cycle:
print('IMPOSSIBLE')
elif certain == False:
print('?')
else:
for r in result:
print(r, end=' ')