▶ 문제 : https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이��
www.acmicpc.net
▶ (참조)위상 정렬 : https://blog.naver.com/ndb796/221236874984
25. 위상 정렬(Topology Sort)
위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ...
blog.naver.com
▶ (참조)deque 사용법 : https://dongdongfather.tistory.com/72
[파이썬 기초] 스택과 큐의 기능을 한번에 deque
deque는 스택과 큐의 기능을 모두 가진 객체로 출입구를 양쪽에 가지고 있다. 스택처럼써도 되고, 큐처럼 써도 된다. 여러가지 메서드를 이용해서 이런 기능을 구현한다. 먼저 deque를 만들어보자 >>> from collec..
dongdongfather.tistory.com
▶ 코드
# 위상 정렬 - 사이클이 없어야 가능하다.
# 단계1) 진입차수가 0인 정점들을 큐에 삽입한다.
# 단계2) 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.
# 단계3) 간선 제거 이후에 진입차수가 0 이 된 정점을 큐에 삽입한다.
# 큐가 빌 때까지 단계2~3을 반복한다.
# 모든 원소를 방문하기전에 큐가 빈다면 사이클이 존재하는것이다.
from collections import deque
import sys
n, m = map(int, sys.stdin.readline().split())
dq = deque()
indegree = [0]*(n+1) # 진입차수 (노드 : 1~N)
tree = [[] for i in range(n+1)] # 트리 구조 (노드 : 1~N)
result = []
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
tree[a].append(b)
indegree[b] += 1
#print('tree=', tree)
#print('indegree=', indegree)
# 단계1
for i in range(1,n+1):
if indegree[i] == 0:
dq.appendleft(i)
#print('dq=', dq)
# 큐가 빌 때까지 단계2 ~ 3 을 반복
while dq:
a = dq.pop() # 단계2
result.append(a)
for b in tree[a]:
indegree[b] -= 1
if indegree[b] == 0: # 단계3
dq.appendleft(b)
#print('result=', result)
for a in result:
print(a, end=' ')
