[プログラマー]コードテスト練習-貪欲レベル3島をつなぐ
Solution.java import java.util.*;
class Solution {
int[] p;
public int solution(int n, int[][] costs) {
int answer = 0;
p = new int[n];
for (int i = 0; i < n; i++) p[i] = i;
Arrays.sort(costs, Comparator.comparingInt(o -> o[2]));
for (int[] cost : costs) {
int a = find(cost[0]);
int b = find(cost[1]);
if (a != b) {
union(a, b);
answer += cost[2];
}
}
return answer;
}
int find(int child) {
if (p[child] == child) return child;
return p[child] = find(p[child]);
}
void union(int a, int b) {
p[b] = a;
}
}
最小身長木問題.union-findアルゴリズムを実現し解決した.
出典:プログラマーコードテスト練習、https://programmers.co.kr/learn/challenges
Reference
この問題について([プログラマー]コードテスト練習-貪欲レベル3島をつなぐ), 我々は、より多くの情報をここで見つけました
https://velog.io/@hye07on11/프로그래머스-코딩테스트-연습-탐욕법Greedy-Level-3-섬-연결하기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.util.*;
class Solution {
int[] p;
public int solution(int n, int[][] costs) {
int answer = 0;
p = new int[n];
for (int i = 0; i < n; i++) p[i] = i;
Arrays.sort(costs, Comparator.comparingInt(o -> o[2]));
for (int[] cost : costs) {
int a = find(cost[0]);
int b = find(cost[1]);
if (a != b) {
union(a, b);
answer += cost[2];
}
}
return answer;
}
int find(int child) {
if (p[child] == child) return child;
return p[child] = find(p[child]);
}
void union(int a, int b) {
p[b] = a;
}
}
Reference
この問題について([プログラマー]コードテスト練習-貪欲レベル3島をつなぐ), 我々は、より多くの情報をここで見つけました https://velog.io/@hye07on11/프로그래머스-코딩테스트-연습-탐욕법Greedy-Level-3-섬-연결하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol