tose33

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 위상정렬 문제. d[] 배열에 큐의 깊이를 기록하면 된다.

https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 위상 정렬을 응용하는 문제다. 위상정렬은 큐를 써서 정렬까지 하지만 이 문제는 정렬이 필요 없으므로 큐는 필요없다. 입력을 받을때 'X를 건설해야 Y를 건설할수 있음' 의 형태로 주어지는데 위상정렬 알고리즘 처럼 entry[Y]++ 해서 Y 건물을 짓기 위해 필요한 건물의 수를 기록하면 된다. 그리고 건물을 건설할떄는 entry[건물] == 0 이라면 건설 가능하고..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬 (topology sort) 문제인데, 노드를 큐에 넣지 않고 우선순위 큐에 넣어주면 되는 문제였다.

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상 정렬 문제. https://tose33.tistory.com/781 백준 1005. ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총. tose33.tistory.com 이..