출처: https://youtu.be/eL-KzMXSXXI
https://www.acmicpc.net/problem/2252
0. 위상정렬이란?
위상정렬은 쉽게 말해 순서가 정해져있는 작업을 차례대로 정렬하는 것이다. 실생활 예로는
- 대학교 선수 과목
- 프로그램 의존도
- 이벤트 스케쥴링
- 제조과정
등등이 있다.
작업의 순서가 정해져있을때 그 작업을 정확하게 정렬해주는 알고리즘이 필요하다.
모든 그래프에 위상정렬을 사용할 수 있는 것은 아니다. 예를들어 순환구조를 가진 그래프는 어느 노드에서 시작해야 할지 정할 수 없기에 위상정렬을 사용 할 수 없다. 또한 위상정렬로 나온 값은 유니크 하지 않다.
위상정렬을 사용할 수 있는 그래프를 Directed acyclic graph(DAG)라고 부른다.
1. 위상정렬을 하는 방법
우선 방문하지 않은 노드를 선택한다. 어느 노드이든 상관이 없다. 이 노드로부터 방문 하지 않은 노드로 DFS를 사용한다. 재귀적인 호출을 사용해 현재 노드로부터 역순으로 정렬 한다.
만약 H가 첫 노드로 선택 되었다면 H -> J -> M 순으로 진행 되고
M 이후 진행 할 수 없으므로 M이 정렬의 가장 마지막으로 간다. 그 이후 J로 백트래킹 이후 L로 이동하고 L 또한 다음 노드가 없으므로 L은 M 앞으로 정렬되고 J로 백트래킹이 이루어진다.
이후 J 또한 인접노드를 모두 방문 했으므로 정렬되고 _ _ _ _ _ _ _ _ _ J L M 이런식이 되는 것이다.
