위상정렬(topological sorting)_백준 2252 줄세우기_파이썬

위상정렬

위상정렬이란

위 이미지와 같이 방향성을 가진 그래의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

 

순서가 정해진 작업을 차례로 수행할때 그 순서를 결정해 주기위해 사용되는 알고리즘으로 

그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬을 이용할 수 있다.

 

위상 정렬이 성립하기 위해서는 반드시 그래프의 사이클이 존재하지 않아야 한다.

즉 위상정렬을 위한 그래프는 Directed Acyclic Graph여야 한다.

 

위상 정렬에서는 답이 여러개일 수 있다.
한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상의 경우 여러답이 존재한다.

 

진입차수, 진출차수

진입차수(Indegree): 특정 노드로 들어오는 간선의 개수

진출차수(outdegree): 특정 노드에서 나가는 간선의 개수

위상정렬의 과정

1. 자기 자신을 가리키는 간선(진입차수) 가 0인 노드를 찾아 큐에 삽입

2. 큐에서 찾은 노드를 pop하고 pop한 노드와 그 노드에서 출발하는 간선 진출차수를 삭제

3. 아직 큐에 노드가 남아있다면 1단계로 돌아가고 큐가 비어있다면 알고리즘을 종료한다.

 

 

백준 2252 줄세우기예제 위상정렬

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

N, M = map(int, input().split())
indegree = [0]*(N+1)
graph = [[]for i in range(N+1)]

for _ in range(M):
    a, b = map(int,input().split())
    graph[a].append(b)
    #a가 b보다 크므로 순서는  a->b
    indegree[b] +=1
    #b로 들어가는 진입차수 1 증가


def topology_sort():
    result = [] #정답 리스트
    q = deque()
    for i in range(1, N+1):
        #진입차수가 0인 노드를 q에 담는다.
        if indegree[i] ==0 :
            q.append(i)
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -=1 #now 에서 나가는 진출차수는 곧 연결된곳의 진입차수 이므로 진입차수 제거
            if indegree[i] == 0:
                q.append(i)
    
    for i in result:
        print(i, end=' ')

topology_sort()