[알고리즘] 위상 정렬(Topological Sort)

위상 정렬 (Topological Sort)

순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘.

 

• 위상 정렬은 DAG (Directed Acyclic Graph, 방향성 비순환 그래프)에서만 사용 가능

 

알고리즘 과정

1. 각 노드(vertex)의 진입간선을 저장한다.
2. 진입간선이 없는 노드를 큐에 push
3. 큐에서 노드를 하나씩 꺼내서 위상정렬에 넣어준다.
4. 꺼낸 노드와 연결된 노드의 위상을 하나씩 낮추고 간선(edge)을 없앤다.
5. 진입간선이 없는 노드를 큐에 다시 넣어준다. 
6. 3-5번을 큐가 빌 때까지 반복한다.

 

동작 예시

"라면 끓이기"에 비유

1.  진입 간선이 0인 노드 Queue에 넣기

 

"라면 끓이기"로 예를 들어보자면, 라면을 끓이기 위해서 우선 [냄비에 물 붓기]와 [라면 사오기]가 라면을 끓여먹기 위한 기초 작업이므로 진입 간선 (해당 노드로 들어오는 간선)이 없다. 따라서 [냄비에 물 붓기 (1)], [라면 사오기(2)] 작업은 진입 간선이 0이고, [물 끓이기(3)]의 진입 간선은 2개, [라면 넣기(4)]는 1개이다.

 

 

 

2.  Queue에서 1 (Queue.front()) 꺼내서 위상 정렬에 넣기

 

이미 queue에 들어갔었던 1, 2를 제외하고 진입 간선이 0인 노드가 없으므로 queue에 아무것도 들어가지 않는다.

 

3. Queue에서 2 꺼내기

Queue에서 꺼낸 2를 위상 정렬에 넣어준다. 2를 꺼내면서 3으로 향하는 진입 간선이 0이 되었으므로 3을 Queue에 push 해준다.

 

 

4. Queue에서 3 꺼내기

마찬가지로 3을 Queue에서 뺀 후 위상 정렬에 넣어준다. 이후 4를 Queue에 push.

 

이후 Queue에서 4를 빼주면 Queue에 아무 것도 없으므로 종료하고, 최종 위상 정렬 결과 [1 - 2 - 3 - 4] 를 확인할 수 있다.

 

 

바로 문제를 풀어보자.

[BOJ] 2252번 '줄 세우기'

소스 코드 (C++)

알고나니 재미있다!