[Python] [BOJ] 줄 세우기(2252)

💡 문제 해결

1. 입력받은 정보를 통해 더 위에 서야할 인원의 차수를 +1
2. 자신보다 뒤에서야 할 사람을 저장
3. 만약 차수가 1이라면 deque에 추가
4. deque에서 pop해가며 뽑은 값의 뒤에 서야 하는 인원들의 차수를 -1
5. 만약 차수가 1이 된다면 deque에 append
6. deque에 값이 존재하는 동안 반복

📌 모든 관계의 정보가 나타나지 않으므로 주의

🧾 문제 설명

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 
각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 
그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

문제보기

🖨 입출력

📝 풀이

from collections import deque

N, M = map(int, input().split())
infos = [tuple(map(int, input().split())) for _ in range(M)]

infos.sort()

parents = [[] for _ in range(N + 1)]
degrees = [1] * (N + 1)
for short, tall in infos:
    degrees[tall] += 1
    parents[short].append(tall)

deq = deque()
for i in range(1, N + 1):
    if degrees[i] == 1:
        deq.append(i)

answer = []
while deq:
    degree = deq.popleft()
    for parent in parents[degree]:
        degrees[parent] -= 1
        if degrees[parent] == 1:
            deq.append(parent)

    print(degree, end=' ')
print()

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/2252