백준145671 [알고리즘] 위상 정렬(Topological Sort) - 개발하는 지토 위상 정렬(Topological Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 이다. 위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조 또는 게임에서의 스킬트리 중 선행스킬이 존재하는 경우이다. 앞선 대표 예 두가지 중 각자 더 이해가 쉬운 예시를 떠올려 보면 쉽게 이해할 수 있을 것이다. 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프에 대해서 위상 정렬을 수행한 결과 값이.. 2021. 3. 18. 이전 1 다음
