황태건블로그

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상 정렬만 구현하면 되는 단순한 문제 이전에 다뤘던 https://xorjsghkd1011.tistory.com/120 위상정렬 풀이에서 언급한 2가지 접근법 (Kahn, DFS) 중 1번 방법을 사용했다. 이번에도 그림과 함께 확인해보자. 0. 그래프를 입력받는다. 위상정렬만 구현하고자 하면 그래프를 이런 식으로 저장하면 된다. 참고로 아래 예시는 일반적인 입력 방식으로, ..

방탄 안티 아닙니다 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 예제 출력 결과를 의식하지 말자. 위상 정렬만 잘 구현하면 된다. 나는 당장 예제 2번의 출력 결과도 3 4 1 2가 나왔지만 정답은 맞았다. 위상 정렬을 구현하는 방법에는 두 가지가 존재한다. 1. Kahn 알고리즘 1) 그래프 최상단에 위치한 정점을 찾는다. 여기서 최상단이란 in-degree가 0인 정점을 말한다. 2) 해당 정점..