위상정렬이라는 것은, 문제를 풀때 참 많이 쓰이는 기본적인 알고리즘이다.
위상 정렬은 DAG 그래프를 기본으로 사용되는데, DAG(Directed Acyclic Graph)는 말 그대로 두가지 속성을 갖는다.
- 방향성이 있다.
- 사이클이 없다.
위상정렬의 원리는, 진입차수가 0개인 것부터 탐색한다는 것이다.
알고리즘의 원리는 다음과 같다.
- 진입차수가 0인 노드들을 탐색한다.
- 1에 해당하는 노드들을 제거한다.
- 1에 해당하는 노드들로 들어가는 간선을 제거한다.
- 1로 돌아간다.
여기서 중요한 점은, 4에서 1로 돌아갈 때, 진입차수가 0개였던 노드들로 들어가는 간선들이 제거됨으로써, 진입차수가 0개인 새로운 노드들이 생겨난다는 것이다.
위상정렬은 주어진 순서를 맞추는 것이라 할 수 있으며, 순서의 조건이 충분하지 않은 경우는 여러 경우의 수가 나올 수도 있다.
//+
위상정렬은 아래와 같은 방식으로 효과적으로 응용 가능하다고 본다.
- 진출차수가 0개인 경우도 같은 방식으로 구현할 수 있다.
- cycle을 발견할 수 있다.
위와 같은 그래프에서, C의 진입차수가 0이므로 제거한다고 해도, A와 B의 진입차수는 모두 1이므로, 더 제거할 수 없으며, cycle이라는 것을 확인할 수 있다.
EmoticonEmoticon