[백준] 3665. 최종 순위 - 파이썬

풀이.

처음에 주어진 순위들의 간선을 모두 처리하고 바뀐 순위의 간선 정보들을 처리하여 풀면된다.

즉 그래프를 통해 사이클이 존재하는지 존재하지 않는지 확인을 하고, 최종 순위를 담는 배열의 길이가 n이 아니라면 불가능의 경우로 하였다.

 

 

소스코드.

 

	import sys
	from collections import deque
	input = sys.stdin.readline
	tc = int(input())
	for i in range(tc):
	n = int(input())
	prev_rank = list(map(int, input().split()))
	rank = [[False] * (n+1) for _ in range(n+1)]
	in_degree = [0] * (n+1)
	for j in range(n):
	for l in range(j+1, n):
	rank[prev_rank[j]][prev_rank[l]] = True
	m = int(input())
	for j in range(m):
	a, b = map(int, input().split())
	rank[a][b], rank[b][a] = rank[b][a], rank[a][b]
	final_rank = []
	queue = deque()
	# 진입 차수 계산
	for j in range(1, n+1):
	in_degree[j] = rank[j].count(True)
	if in_degree[j] == 0:
	queue.append(j)
	# 위상 정렬
	while queue:
	cur = queue.popleft()
	final_rank.append(cur)
	for j in range(1, n+1):
	if rank[j][cur]:
	in_degree[j] -= 1
	if in_degree[j] == 0:
	queue.append(j)
	if len(final_rank) == n:
	print(*final_rank[::-1])
	else:
	print("IMPOSSIBLE")

view raw 3665 - 최종 순위.py hosted with ❤ by GitHub