백준/위상 정렬
-
백준 3665 nodejs백준/위상 정렬 2023. 3. 9. 17:27
문제 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 간선 정보를 2차원 배열의 인접행렬 정보로 저장하고, 수정된 순위에 맞춰 바꿔준다. 위상 정렬을 이용하여 답을 구한다. let [, ...I] = `${require('fs').readFileSync(0)}`.trim().split`\n`.map(e => e.split` `.map(Number)) let [i, O] = [0, []] while (i < I.length) { co..
-
백준 1766 nodejs백준/위상 정렬 2023. 3. 8. 14:26
문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 위상정렬을 이용한다. 최솟값 힙을 이용해, 풀 수 있는 문제를 크기가 낮은 순으로 정렬한다. let [[N], ...I] = `${require('fs').readFileSync(0)}`.trim().split`\n`.map(e => e.split` `.map(Number)) class Heap { constructor() { this.A = [] } pu..
-
백준 2623 nodejs백준/위상 정렬 2023. 3. 7. 15:18
문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 위상 정렬 알고리즘을 활용한다. 사이클이 생길 경우 모든 노드를 방문하지 못함을 이용하여 예외 처리한다. let [[N], ...I] = `${require('fs').readFileSync(0)}`.trim().split`\n`.map(e => e.split` `.map(Number)) const [G, deg, O, Q, V] = [[...Array(N + 1)]..
-
백준 1005 nodejs백준/위상 정렬 2023. 3. 3. 20:20
문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 위상 정렬 알고리즘과 DP를 이용한다. let [, ...I] = `${require('fs').readFileSync(0)}`.trim().split`\n`.map(e => e.split` `.map(Number)) let [i, O] = [0, []] while (i < I.length) { const [[N, K], D] = [I[i], [0, ...I[++i]]] const..
-
백준 2252 nodejs백준/위상 정렬 2022. 12. 25. 16:46
문제 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 풀이 위상 정렬을 이용하여 결과를 구한다. DFS let [[N], ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e => e.split(' ').map(Number)) const graph = [...Array(N + 1)].map(_ => [])..