백준/최소 스패닝 트리
-
백준 1647 nodejs백준/최소 스패닝 트리 2022. 12. 22. 17:26
문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 최소 스패닝 트리를 만든 후, 비용이 가장 큰 길 하나를 빼 2개로 분리한다. (최소 스패닝 트리 만드는 법은 1197번 참조) let [[N], ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e => e.split(' ').map(Number)) ..
-
백준 1197 nodejs백준/최소 스패닝 트리 2022. 12. 21. 17:00
문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 Kruskal과 Union-Find 알고리즘을 활용한다. (참조한 블로그) let [[V], ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e => e.split(' ').map(Number)) I.sort((a, b) => a[2] - b..