위상 정렬

[백준] 2623. 음악프로그램 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 보자마자 위상 정렬부터 생각이 났다. 근데 문제에서 사이클이 있을 수 있다는 것을 명시함. (위상 정렬은 사이클이 없을 때 적용 가능.) 처음에는 Union-Find를 이용해 미리 사이클이 있는 지를 검증하고 해야하나 생각했으나, 굳이 그러지 않아도 진행 과정에서 사이클이 존재한다면, N개를 모두 돌지 못하고 종료되므로 예외처리에 넣어줌. from co..

[백준] 2252. 줄 세우기 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 [백준] 1005. ACM Craft - 파이썬 [백준] 2056. 작업 - 파이썬 최근 위 문제들과 같은 위상 정렬 문제를 몇 번 풀어서인지, 문제를 보고 얼마 지나지 않아 위상 정렬로 해결할 수 있겠다는 생각이 들었다. 모든 vertex가 edge로 연결되어 있지도 않고, "답이 여러 가지인 경우에는 아무거나 출력한다." 라는..

[백준] 2056. 작업 - 파이썬

[Gold IV] https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net [백준] 1005. ACM Craft - 파이썬 과 매우 유사했던 문제. 풀이 [백준] 1005. ACM Craft - 파이썬 과 매우 유사해서 비슷하게 어려움 없이 풀었던 문제. DP와 위상 정렬(Topological Sort) 을 이용해서 풀이했다. from collections import deque N = int(input()) times = [] graph_in..

[백준] 1005. ACM Craft - 파이썬

[Gold III] https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net [위상 정렬(Topological Sort)] 참고. https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html 풀이 1 위상 정렬(Topological Sort)을 이용하여 풀이. 오답이 나왔는데, 잘 생각해보니 각 턴마다 건설 시간이 가장 긴 것을 더하는 것이 총 건설 시간의 합이 최소가 되도록 하지..