Dev_Diary

https://www.acmicpc.net/problem/14567역시 전형적인 위상정렬 문제입니다.위상정렬 리스트를 만들어 순회를 하되, 순회가 가능해도 한번에 순회하는 것이 아닌 학기마다 끊어서 가능한 수업을 모두 큐에 넣어주어야 합니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, M, subjects): # 위상정렬 리스트 / [[들어오는 노드], 이수한 학기, [나가는 노드]] topol_list = [[set(), 0, set()] for _ in range(N+1)] for A, B in subjects: topol_list[A][2].add(B) top..

https://www.acmicpc.net/problem/2056전형적인 위상정렬 문제입니다.들어오는 노드와 나가는 노드를 정리해준 뒤 시간을 누적하며 들어오는 노드를 모두 탐색한 노드를 탐색하면 됩니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, works): # 위상정렬 그래프 / [[들어오는 노드들], 소요 시간, [나가는 노드들]] topol_graph = [[[], 0, []] for _ in range(N+1)] for w in range(len(works)): # 소요 시간 topol_graph[w+1][1] = works[w][0] # 입..

https://www.acmicpc.net/problem/2637위상정렬 문제입니다. 간단하게 생각해보면 DFS 나 BFS 를 사용해 한 부품씩 곱해 더해주면 될 것 같지만 단계나 부품의 수가 복잡해지고 배수가 늘어나면 시간이나 메모리가 부족해집니다. 그렇기에 조금 더 효율적으로 단계를 진행할 필요가 있습니다. 그렇기에 단계별로 개수를 병합해 한번에 곱하는 식으로 진행하면 비교적 효율적으로 진행할 수 있습니다.위 방법으로 진행할 때 모든 중간부품의 개수를 카운트하지 않았을 때 다음 단계를 계산해버리면 오류가 생기므로 중간부품의 개수가 모두 카운트 될 때 다음 단계로 넘어가야 하는데, 이 때 위상정렬을 사용할 수 있습니다. B 부품을 만들기 위해 A 부품이 필요하다고 할 때(A->B) 'B 부품 노드에 A..

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 백준 2252 Python https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다 dev-diary-0717.tistory.com 파이..