BOJ [줄 세우기]

문제

문제 보기

두 명씩 키를 비교한 결과만 m개 주어질 때 전체 학생을 키 순서로 정렬하라는 문제이고 답이 여러개일 때 그 중에서 아무거나 출력하라는 문제이다.

풀이

[출처: https://m.blog.naver.com/ndb796/221236874984]

위의 방식으로 문제를 해결하였다.

check[큰 친구] = [작은 친구1, 작은 친구2, ...]
graph[작은 친구] = [큰 친구1, 큰 친구2, ...]

추가로 시간초과를 해결하기 위해서 다음 두 가지의 list를 설정하였는데 check는 set으로 구현하였다. => in 연산을 해야하므로

또한 while문에서 q를 pop한 뒤 해당 친구와 관계를 맺는 친구를 graph로부터 가져와서 해당 친구만 check 하여 시간을 줄였다. graph가 없으면 1~n 까지 모두 탐색해야한다.

코드

from collections import defaultdict, deque

n,m = map(int,input().split())
check = defaultdict(set)
graph = [[] for _ in range(n+1)]
q = deque([])

for i in range(1,n+1):
	q.append(i)

for _ in range(m):
	a,b = map(int,input().split())
	check[b].add(a)
	graph[a].append(b)
	if b in q:
		q.remove(b)

answer = []

while q:
	now = q.popleft()
	answer.append(now)
	for i in graph[now]:
		if now in check[i]:
			check[i].remove(now)
			if len(check[i]) == 0:
				q.append(i)


for i in range(len(answer)-1):
	print(answer[i], end = ' ')

print(answer[-1])