# topological
[ 백준 ] 2623 음악프로그램
Link | [백준 2623번 문제 : 음악프로그램] (https://www.acmicpc.net/problem/2623) 📌 About 특정 가수의 순서가 오려면 이전 가수들의 순서가 선행되어야 한다. Graph 입장에서 보면 node의 탐색에 선행 node 탐색이 필요하다. 그렇기 때문에 위상정렬을 통해 해결할 수 있다. 위상 정렬 📌 Solution Step 1. 진입차수와 진출 node를 저장하는 자료구조를 초기화한다. preSingerNum[n]은 n번 가수보다 선행되어야 할 가술들의 수이다. nextSingers.get(n)은 n번 가수 이후에 오는 가술들이다. 이 때 Set가 아닌 List으로 하면 중복이 될 수 있기 때문에 Set으로 선언한다. **Step 2.
백준 - 2623번 음악프로그램
https://www.acmicpc.net/problem/2623 접근법 기본적인 위상정렬문제로 쉽게 해결! 위상정렬의 핵심은 inDegree 배열. 각 인덱스별로 앞서 필요한 항목의 수 만큼 count를 가지고 있고, 조치가 취해지면 count를 깍아나가는 식으로 접근하면 됨 graph는 선행 -> 후행의 관계를 잡기위해 마련한 변수. 입력에 따라 선행, 후행 관계를 graph 배열의 인덱스에 맞게 생성. 생성하면서 후행이 되는 인덱스는 inDegree 배열 값도 올려줌 초기에는 inDegree배열이 0인 값 = 선행조건이 없는 값을 Queue에 넣어주고 반복문 소스
백준 - 1766번 문제집
https://www.acmicpc.net/problem/1766 접근법 기본적인 위상정렬문제로 해결 graph라는 List배열을 할당해주고, 각각 인덱스에 후속작업의 인덱스를 넣어줌. graph[pre].add(post) 넣어주면서, 전 작업이 필요한 경우 count를 올려줌. inDegree[post]++ >4번은 1번 앞에 있어야함 => graph(1).add(4), 5번은 1번 앞에있어야함 => graph(1).add(5) inDegree의 값이 0인 인덱스에 대해 우선순위 큐에 삽입 (문제에서 숫자가 빠른순으로 처리하라는 내용이 있으므로 우선순위 큐를 사용함) 우선순위 큐에 맞게 꺼낸 항목에 대해, 후속작업 List를 탐색하고 각각에 대해 inDe