알고리즘 - 위상정렬
·
문제 풀이/백준 문제풀이
위상 정렬(Topological Sort)이란?위상 정렬(Topological Sort)은 방향 그래프에서 노드들을 선후관계를 따져 정렬하는 알고리즘입니다. 이 알고리즘은 DAG(Directed Acyclic Graph), 즉 사이클이 없는 방향 그래프에서만 동작합니다. 위상 정렬은 작업의 순서가 중요한 문제에서 자주 사용됩니다. 예를 들어, 프로젝트 관리에서 작업 간의 의존 관계를 정의하고, 작업을 어떤 순서로 수행해야 하는지를 결정할 때 사용할 수 있습니다.위상 정렬의 주요 개념방향 그래프: 그래프에서 간선이 방향을 가지며, 노드 간의 관계가 단방향인 그래프입니다.사이클 없음: 그래프 내에 자기 자신으로 돌아오는 경로가 없어야 합니다. 사이클이 존재하면 위상 정렬을 할 수 없습니다.진입 차수: 특정 ..