[Python] BOJ 2252 - 줄 세우기

www.acmicpc.net/problem/2252

2252번: 줄 세우기

전형적인 위상정렬 문제이다.

위상정렬 알고리즘은 추후에 한 번 포스팅 할 예정이다.

 

1. N, M을 입력받고 M번 만큼 A와 B를 입력받는다.

2. A가 B 앞에 줄 서야 하므로 graph[A]에 B를 append해주고 indegree[B]에 1을 더해준다.

   (indegree 배열: 진입차수)

3. indegree[1]부터 indegree[N]까지 돌며 진입차수가 0인 노드를 큐에 삽입한다.

4. 큐가 빌 때까지 큐에서 원소를 꺼내고 그 원소와 연결된 노드들을 지운다(진입차수에서 1 빼기)

   꺼낸 원소를 출력하면 끝!

from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)
for _ in range(M):
	A, B = map(int,input().split())
	graph[A].append(B)
	indegree[B] += 1
 
def topologySort():
	result = []
	q = deque()
	# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
	for i in range(1, N+1):
		if not indegree[i]:
			q.append(i)
	
	# 큐가 빌 때까지 반복
	while q:
		# 큐에서 원소 꺼내기
		x = q.popleft()
		result.append(x)
		# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
		for i in graph[x]:
			indegree[i] -= 1
			if indegree[i] == 0:
				q.append(i)
		print(x, end = ' ')
topologySort()

(solved.ac 티어: 골드2)

 

# 비슷한 위상정렬 문제들:

www.acmicpc.net/problem/1005

www.acmicpc.net/problem/2623

www.acmicpc.net/problem/1516