위상정렬

[백준 2623] 음악프로그램 C++

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상 정렬 1. 문제 해결 아이디어 indegree를 활용한 위상 정렬로 풀었다. 입력을 받을 때 각 정점마다 indegree가 몇 개 인지 배열에 저장해준다. 위상 정렬 bfs를 수행하면서 현재 정점의 자식 정점들의 indegree를 하나씩 빼준다. 만약 자식 정점의 indegree가 0이 된다면 현재 정점을 queue에 넣어준다. queue에 넣는다는 의미는 자신보다 먼저 수행되어야 할 정점이 없어서 현재 정점을 바로 실행해도 무방하다는 ..

[백준 1005] ACM Craft C++

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 1. 문제해결 아이디어 indegree를 활용한 위상 정렬을 하는 문제이다. 위 그림에서 각각의 phase는 다음 phase로 넘어가기위해 모두 해결해야하는 과제와도 같다. 예를 들어서 phase2에서 phase3로 넘어가려면 phase2에 있는 건물을 모두 건설해야 넘어갈 수 있다. 따라서 phase2에서 가장 오래걸리는 건물이 해당 phase에서 걸리는 시간이 되고, 이전 phase의 최대 시간만큼만 next phase의..