나그네

1005번: ACM Craft 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 1516번 문제와 비슷한 문제로 각 건물을 짓는 데는 먼저 지어져야 하는 건물이 있으므로 위상 정렬을 해야 한다. 특정 건물이 완성되기까지 걸리는 시간은 이전 건물이 완성되기까지 걸리는 최대 시간 + 특정 건물을 짓는 시간이다. 그리고 이전 건물에 대해서도 같은 과정을 반복하게 된다. 따라서 DP 테이블을 만들어 (누적 값 + 현재 추가 값)이 최대가..

1766번: 문제집 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘에 추가적인 정렬 기준이 추가된 문제다. 기본적으로 일반적인 위상정렬과 같이 indegree 배열의 값이 0인 것들을 큐에 넣는데, 가능한 쉬운(번호가 작은) 문제부터 풀어야 하므로 큐 대신 최소 힙을 사용한다. STL에서 우선순위 큐..

1516번: 게임 개발 문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 각 건물을 짓는 데는 먼저 지어져야 하는 건물이 있으므로 위상 정렬을 해야 한다. 그리고 각 건물이 완성되기까지 걸리는 최소 시간을 출력해야 하므로 위상 정렬하는 순서에 따라 시간을 계산해 주면 된다. 위상 정렬은 큐에 들어가고 나오는 순서대가 정렬된 순서이므로 차례대로 작업을 수행한다. 기본적으로 각 건물을 완성하는 데 걸리는 시간은 그 건물을 완성하..

2252번: 줄 세우기 문제 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 풀이 여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘을 사용하는 문제로 거저 주는 문제다. 각 순서를 입력받을 때마다 u -> v 간선을 추가하고 뒤의 인덱스의 indegree 배열의 값을 1 증가시킨다. indegree 배열의 값이 0인 정점을 모두 큐에 추가하고 차례..

2623번: 음악프로그램 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘을 배울 때 푸는 문제다. 각 순서를 입력받을 때마다 [앞->뒤]의 간선을 추가하고 뒤의 인덱스의 indegree 배열의 값을 1 증가시킨다. indegree 배열의 값이 0인 정점을 모두 큐에 추가하고 차례대로 front 원소에 대해 탐색..