재원블로그 재원블로그

위상 정렬은 순서가 정해진 일들에 대해서 그 순서를 위배하지 않고 일들의 처리 순서를 만드는 방법을 만드는 알고리즘이다. 대표적으로 선수 과목을 예로 들 수 있다. C 과목을 들으려면 B를 들어야 하고, B 과목을 들으려면 A 과목을 들어야 한다고 하자. 그러면 수강 순서는 A -> B -> C 가 될 것이다. 이 순서를 만드는 것이 위상 정렬이다. 위상 정렬은 DAG (Directed Acyclic Graph) 에서만 성립한다. 즉, 유향 그래프여야 하며, 사이클이 없어야 한다. 무향 그래프의 경우 A -> B 와 B -> A 가 모두 가능하여 선수 과목이라는 조건에 모순이다. 또한 C를 듣기 위해서 B를 듣고, B를 듣기 위해서는 A를 듣는데, 이 때 A를 듣기 위해서 C를 들어야 한다면 이 또한 모..