[백준 - Python] 2252 - 줄 세우기

0.  문제 링크

 

 

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

2252번: 줄 세우기

---

1.  풀이 방법

 

 

2023.08.13 - [Computer Science/알고리즘] - [백준 - Python] 1766 - 문제집

[백준 - Python] 1766 - 문제집

위의 문제처럼 위상 정렬을 사용해서 푸는 문제이다.

---

2.  코드

 

 

import sys
from collections import deque
input = sys.stdin.readline


if __name__ == "__main__":
    n, m = map(int, input().split())
    subSequenceList = [[] for _ in range(n + 1)]        # 내 뒤에 오는 애들
    degree = [0] * (n + 1)      # 내 앞에 몇개 필요한지
    dq = deque()
    ans = []

    for _ in range(m):
        a, b = map(int, input().split())
        subSequenceList[a].append(b)
        degree[b] += 1

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

    while dq:
        prior = dq.popleft()
        ans.append(prior)
        for sub in subSequenceList[prior]:
            degree[sub] -= 1
            if degree[sub] == 0:
                dq.append(sub)

    print(*ans, sep=' ')

---

3.  마무리