[백준] 2252번: 줄 세우기 - python

https://www.acmicpc.net/problem/2252

 

DAG 위상정렬을 이용한 문제

 

degree에 차수를 저장하고, 0인 차수를 큐에 넣음으로써 시작된다. 

그 후 큐를 뽑아내며 그와 연결된 그래프의 차수를 감소하며 0일 경우에 큐에 삽입하여 큐가 빌때까지 이 작업을 반복한다.

 

처음에 인접행렬로 구현했으나 메모리초과로 인접리스트로 구현하니 메모리문제가 해결되었다.

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
degree = [0] * (n+1)
arr = [[] for _ in range(n+1)]
dq = deque()
for _ in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    degree[b]+=1

for i in range(1, n+1):
    if degree[i] == 0:
        dq.append(i)

while dq:
    now = dq.popleft()
    print(now, end=" ")
    for i in arr[now]:
        degree[i]-=1
        if degree[i] == 0:
            dq.append(i)

 

완성