문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 한 문제, 한 문제씩 풀어나가는 것을 그래프에 대입하여 노드를 탐색하는 과정으로 생각해봅시다. 조건에 의해 모든 노드를 탐색해야 하고, 먼저 푸는것이 좋은 문제를 반드시 먼저 풀어야 하므로 선행 노드를 반드시 탐색해야 합니다. 따라서 위상정렬로 문제를 해결해야 합니다. 그런데 쉬운 문제(번호가 낮은 노드)부터 해결해야 하므로 현재 풀 수 있는 문제(inde..
위상 정렬
문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 각 건물마다 선행되어 지어져야할 건물이 존재하기 때문에 위상정렬 문제입니다. 건물마다 들어오는 화살표(indegree)를 저장하고, 자신이 탐색될 때마다 화살표를 하나씩 지우며 화살표의 개수가 0이 될 경우 자신의 건물을 짓고 다음 탐색을 진행합니다. 이때 각 건물들은 독립적으로 지어질 수 있기 때문에 먼저 지어진 건물들을 우선적으로 처리하기 위해 BFS탐색에 우선순위 큐를 활용합..
