[백준] 줄 세우기 (Python 파이썬 풀이)

Problem Point

학생들간의 순서를 보여주고 줄을 세우는 경우의 수를 말한다. 이렇듯 순서를 중요시 여기는 문제에서는 위상정렬을 떠올리면 풀이시간을 줄일 수 있다.

문제출저 : https://www.acmicpc.net/problem/2252

문제에서 요구하는 값들을 받고 간선을 받아서 딕셔너리 형태로 저장한다. 또 한 위상을 알기 위해서 따로 리스트로 저장하기 위해 degree 리스트를 선언하였다.
덱을 선언하여 전에 입력받은 순서대로 위상을 확인하도록 하였다. 그 후 각 연결된 노드를 순회하며 위상을 감소시키며 결과값을 도출한다.

최종풀이

from collections import deque, defaultdict
M,N=map(int,input().split())

queue=deque()
key= defaultdict(lambda: [])
degree=[0 for i in range(M+1)]
answer=[]

for i in range(N):
    a ,b =map(int,input().split())
    key[a].append(b)
    degree[b]+=1
for i in range(1,M+1):
    if degree[i]==0:
        queue.append(i)
while queue:
    start=queue.popleft()
    answer.append(start)
    for i in key[start]:
        degree[i]-=1
        if degree[i]==0:
            queue.append(i)
print(*answer)