반응형 위상정렬7 백준 2637번 장난감 조립 - C++ 풀이 1. 위상 정렬을 사용하여 각 부품을 조립하기 위한 부품의 개수를 누적 계산한다. 1. 위상 정렬을 사용하여 각 부품을 조립하기 위한 부품의 개수를 누적 계산한다. 부품들 간에 선행 관계가 존재하므로 위상 정렬을 사용해서 해결할 수 있다. 위상 정렬 과정에서 각 부품을 만들기 위한 기본 부품의 개수를 누적해서 계산해준다. #include #include #include using namespace std; typedef pair pii; int N, M; vector indegree(101); vector adjs[101]; vector topologySort() { vector parts(N+1, vector(N+1, 0)); queue q; for (int i=1; i N >> M; for (int .. 2022. 8. 3. 백준 1766번 문제집 - C++(cpp) 풀이 1. 각 문제를 그래프의 정점으로 생각한다. 2. A번 문제를 B번 문제보다 먼저 푸는 것이 좋다면 A에서 B로 가는 방향 간선을 추가한다. 3. 우선순위 큐를 가지고 위상 정렬한다. 1. 각 문제를 그래프의 정점으로 생각한다. 선행 관계가 주어진 작업들의 작업 순서를 결정하는 것은 위상 정렬로 풀 수 있다. 먼저 주어진 상황을 그래프로 변환해야 한다. 각 문제를 정점으로 생각해준다. 2. A번 문제를 B번 문제보다 먼저 푸는 것이 좋다면 A에서 B로 가는 방향 간선을 추가한다. 그리고 A가 B보다 선행되어야 한다면, A에서 B로 가는 방향 간선을 추가한다. 3. 우선순위 큐를 가지고 위상 정렬한다. 완성된 그래프를 가지고 위상 정렬을 수행한다. 그런데 "가능하면 쉬운 문제부터 풀어야 한다."는 조건을 .. 2022. 2. 4. 백준 2623번 음악프로그램 - 스위프트(Swift) 풀이 1. 각 출연자를 정점으로 생각하고, 보조 PD들이 만든 순서가 A B C D라면 A→B, B→C, C→D로 가는 간선을 추가한다. 2. 완성된 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 결과에 포함된 정점 개수가 N개가 아니라면 순서를 정하는 것이 불가능한 경우이다. 1. 각 출연자를 정점으로 생각하고, 보조 PD들이 만든 순서가 A B C D라면 A→B, B→C, C→D로 가는 간선을 추가한다. 선행 관계가 주어진 작업들의 순서 정하기 문제이다. 위상 정렬 알고리즘을 사용하여 해결할 수 있다. 현재 상황을 그래프로 변환한다. 보조 PD들이 만든 X명의 순서를 차례로 쪼개면 X-1개의 선행 관계가 나오게 된다. 위와 같이 선행 관계로 쪼개 간선을 추가해준다. 2. 완성된 그래프에 대해 위상 정렬.. 2022. 1. 28. 백준 2056번 작업 - C++(cpp) 풀이 1. 각 작업을 정점으로, 작업 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 작업에 걸리는 시간을 구한다. 4. max(totalCost[i])를 출력한다. 1516번 게임 개발 문제와 똑같으니 1,2,3번 풀이는 아래에서 확인! 백준 1516번 게임 개발 - C++(cpp) 풀이 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다. 1 please-amend.tistory.com 4. max(t.. 2022. 1. 28. 백준 1516번 게임 개발 - C++(cpp) 풀이 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다. 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 이렇게 선행 관계가 정해져있는 작업들을 순서대로 수행하는 상황은 그래프 위상 정렬 알고리즘으로 해결할 수 있다. 먼저 주어진 상황을 그래프로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 위상 정렬을 해준다. 아래 코드에서는 큐를 사용하였고, 선행 작업들이 모두 완료된 작업들만 큐에 들어가게 된다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물.. 2022. 1. 28. 이전 1 2 다음 반응형
