줄 세우기
-
[백준][Kotlin] 2252번 줄 세우기백준 2023. 4. 13. 14:25
해당 문제는 위상 정렬을 이용하여 작성 할 수 있는 문제 였습니다. 위상 정렬 (Topological sorting)은 유향 그래프에서 정점들을 순서대로 나열하는 것을 말합니다. 이때, 그래프에서 간선은 항상 정점들 사이의 의존 관계를 나타내며, 위상 정렬은 이러한 의존 관계를 지켜가며 모든 정점을 나열하는 작업입니다. 위상 정렬의 핵심 아이디어는 "진입 차수(in-degree)" 개념입니다. 정점의 진입 차수란 그래프에서 들어오는 간선의 수를 의미합니다. 위상 정렬에서는 진입 차수가 0인 정점을 선택하여 정렬 순서에 추가하고, 이 정점과 연결된 간선을 제거한 뒤에 남은 그래프에서 다시 진입 차수가 0인 정점을 선택하여 반복적으로 정렬합니다. 만약, 그래프가 사이클을 포함하고 있다면, 위상 정렬을 할 수..