topological sort4

• 

  [백준/BOJ] 1005번: ACM Craft 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 해설 선행 순서가 정해져 있고, 이를 특정 건물을 짓기까지 얼마나 오랜 시간이 걸릴지 구해야 한다. 선행 순서가 있는 문제에서 전체적인 순서를 구할 때 위상 정렬을 사용한다. 문제의 예제 2번을 보며 풀이를 해보자. 우선 차수가 0인 1번 정점부터 시작을 한다. 위상 정렬을 진행하므로 1번 정점을 큐에 넣고, 이와 연결된 간선들을 모두 제거한다. 이제 차수가 0인 것은 2번과 3번이다... PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 1766번: 문제집 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 해설 문제들의 선행 순서를 입력으로 받고, 이를 이용하여 순서를 짜야한다. 또한 문제의 난이도는 1번 문제가 가장 쉽고 N번 문제가 가장 어려우며, 가능한 쉬운 문제부터 문제를 풀어야 한다. 이러한 유형의 문제는 위상 정렬을 이용하여 해결할 수 있다. 위상 정렬을 이용하나, 이 문제에서는 문제의 난이도까지 고려해야하고, 이는 문제의 번호가 낮을수록 쉽우므로 우선.. PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 2623번: 음악프로그램 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 해설 보조 PD 3명이 담당한 가수들의 순서를 정한다. 이때 한 가수를 여러 보조 PD가 담당할 수 있다. 이렇듯 이미 순서가 정해져 있고, 선행 순서를 위배하지 않으면서 순서를 정하는 것은 위상 정렬(topological sort) 알고리즘을 사용하면 된다. 위상 정렬은 여러 가지 답이 나올 수 있으므로, 코드를 어떻게 짜냐에 따라 답이 달라질 수 있다. 코드 impor.. PS(Problem Solving)/BOJ 2022. 9. 10.

• 

  [알고리즘] 위상 정렬(Topological Sort) 위상 정렬(Topological Sort) 순서가 정해져 있는 작업을 어떠한 차례로 수행해야 하는지 결정해주는 알고리즘이다. 즉, 방향 그래프에 존재하는 정점들의 선행 순서를 위반하지 않고 모든 정점을 나열하는 것이다. 위상 정렬은 한 방향 그래프에서 여러 위상 정렬이 가능하다. 즉, 답이 여러가지일 수 있다는 것이다. 위 방향그래프에서 위상 정렬을 한 결과를 생각해보면 다음과 같다. 1 → 6 → 2 → 5 → 4 → 3 6 → 2 → 1 → 5 → 4 → 3 6 → 1 → 2 → 5 → 4 → 3 과정 진입 차수가 0인 정점을 큐에 저장한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 간선 제거 이후 진입 차수가 0인 정점을 큐에 저장한다. 큐가 빌 때까지 반복한다. 이때, 모든 원소를 방문하.. Algorithm 2022. 9. 10.