1. 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 2. 풀이 문제에서 핵심으로 생각한 부분은 "특정 건물을 짓고 다음 건물을 지을 수 있다" 부분이다. 이는 위상정렬의 "특정 과목을 수강한 후에 다른 과목을 수강할 수 있다"와 같다고 볼 수 있다. 기본적인 위상정렬과 같은 로직으로 돌아가지만 조금 다른 부분이 있다. 바로 건물을 짓는 시간에 대한 부분이다. 문제의 그림에도 나와 있는 예제 입력 1번을 보면, 1번 건물과 연결된 2..
1. 문제 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. 풀이 문제에서 A 다음에 B가 나올 경우 A가 B보다 앞에 있어야 하므로 인접 리스트로 생각한다면 A 노드 다음에 B노드가 연결되어 있다고 생각할 수 있다. 그리고 1 3 이 주어졌을 때 3 1이 또 주어지는 경우는 없으므로 한 방향으로만 흐른다. 노드 다음 특정 노드를 연결하고 이를 순서대로 출력해야 하므로 위상 정렬을 생각할 수 있다...
1. 문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 2. 풀이 백준 분류에 DFS로 분류되어 있는 문제이다. 문제를 보면 학생들이 자기 자신을 팀원으로 고를 수 있고, "학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다" 라고 되어있다. 이는 노드끼리 사이클이 ..
1. 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 2. 풀이 위상 정렬 문제이다. 위상 정렬이 어떤 알고리즘인지 모르거나 혹은 알고 있는데 헷갈리다면 아래 문제를 먼저 풀어보고 이 문제를 보는 것도 좋다. https://sorryday.tistory.com/76 [BOJ] 백준 2623 - 음악프로그램 풀이 1. 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그..
1. 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 위상 정렬 비순환 방향 그래프에서 정점을 선형으로 정렬한 것을 의미 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 방향 그래프(Directed Aclic Graph)여야 한다. 3. 위상 정렬 구현 방법(BFS) ..
