[백준/파이썬] 2252번 줄 세우기

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

2252번: 줄 세우기

처음 풀어본 위상정렬 문제이다!

 

위상정렬을 풀기 위해선 반드시 이용해야하는것이 있다.

1. 진입차수

2. 스택 또는 큐

3. 사이클 여부

 

각 노드를 가리키는 엣지가 몇개 인지(= 진입차수) 계산해주어야 하며, 스택 또는 큐 자료구조를 이용하고, 만약 그래프가 사이클이 존재할 경우에는 위상정렬 순서를 구할 수 없으므로 유의해주자.

 

또한 위상정렬을 푸는 알고리즘은 다음과 같다.

 

우선 배열에 입력을 저장해준 뒤, 배열을 탐색하여 진입차수를 계산함과 동시에 방향 그래프를 만들어준다.

그리고나서 진입차수가 0인 노드를 큐에 넣어준다.

이제 큐가 빌 때  까지 반복하는데, 우선 큐에서 노드 하나를 꺼낸다. 꺼낸 노드에 연결된 엣지들을 모두 제거한다.(제거 = 꺼낸 노드와 연결된 노드의 진입차수 1 감소)

그리고 만약 엣지 제거 이후 진입차수가 0이 되었다면 그 노드를 큐에 넣어준다.

큐에 있는 노드 하나를 탐색할 때 마다 해당 노드를 출력해주면, 그 결과가 바로 위상정렬 결과이다!

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

def topology_sort():
    while q:
        num = q.popleft()
        for i in graph[num]:
            inDegree[i] -= 1
            if inDegree[i] == 0:
                q.append(i)
        print(num, end = ' ')
        
n,m = map(int,input().split())
graph = [[] for _ in range(32001)]
arr=[]
inDegree = [0 for _ in range(32001)]
q = deque()

for _ in range(m):
    big, small = map(int, input().split())
    arr.append((big,small))
    
for big,small in arr:
    inDegree[small]+=1
    graph[big].append(small)
    
for i in range(1, n + 1):
    if inDegree[i] == 0:
        q.append(i)
    
topology_sort()