위상 정렬

문제: ACM Craft (백준 1005번)문제 분석문제 개요:각 건물마다 건설에 걸리는 시간이 주어지고, 특정 건물을 짓기 위해 먼저 지어져야 하는 건물들의 관계(선행 조건)가 주어진다.목표는 주어진 목표 건물 W를 짓기 위한 최소 건설 시간을 구하는 것이다. 핵심 아이디어:위상 정렬:선행 조건을 고려한 건설 순서를 결정하기 위해 위상 정렬을 사용한다.indegree(진입 차수)를 활용해 선행 조건이 없는 건물부터 처리한다.DP (동적 계획법):각 건물을 짓기 위한 최소 시간을 dp 배열에 저장한다.특정 건물의 최소 건설 시간은, 해당 건물에 선행하는 모든 건물들의 건설 시간 중 최대값에 현재 건물의 건설 시간을 더한 값이다.(즉, 선행 건물 중 가장 늦게 완공되는 시점을 고려하여 건물을 지어야 한다...

문제: 음악 프로그램 (백준 2623번)문제 분석이 문제는 사이클 탐색과 위상 정렬을 결합한 문제이다.지문은 길지만, 문제의 핵심은 주어진 조건에 따라 유방향 그래프를 만들고, 그 그래프에서 사이클이 있는지 확인한 뒤, 사이클이 없다면 위상 정렬을 수행하는 것이다.해결 접근사이클 탐색각 가수 간의 선후 관계를 유방향 그래프로 표현한다.사이클이 있으면 그 그래프는 위상 정렬이 불가능하다.DFS를 사용하여 그래프에서 사이클을 탐지한다.위상 정렬사이클이 없으면 위상 정렬을 통해 가수들의 순서를 결정한다.위상 정렬은 진입 차수가 0인 노드를 먼저 처리하며, 이를 통해 순서를 구한다.우선순위 큐위상 정렬을 수행하는 중에 여러 노드가 진입 차수가 0일 때, 우선순위 큐를 사용하여 가장 작은 번호부터 처리하도록 한다..