쌓고 쌓다
[프로그래머스] 섬 연결하기 Java 풀이 및 해설 본문
https://school.programmers.co.kr/learn/courses/30/lessons/42861
풀이 방법
싸이클이 없이 최소 비용으로 모든 노드를 연결하는 최소 비용 신장 트리를 구하면 된다.
최소 비용 신장 트리를 구하기 위한 알고리즘으로 크루스칼을 사용하였다.
여기에 Union-Find 알고리즘도 사용된다.
처음에 DFS로 최소 비용 신장 트리를 구하면 되는게 아닌가 싶었는데
DFS는 한 노드에 하나의 노드만 연결되게(진행 방향으로만) 탐색하기에 아래의 그림을 예로
0번 노드에서 1과 2번 노드가 연결된 상황이 나올 수가 없다..
전체 코드
import java.util.*;
class Solution {
public int solution(int n, int[][] costs) {
int answer = 0;
Arrays.sort(costs, (o1, o2) -> {
return o1[2] - o2[2];
});
int parent[] = new int[101];
for(int i=1; i<=n; i++) {
parent[i] = i;
}
for(int i=0; i<costs.length; i++) {
if(find(costs[i][0], parent) != find(costs[i][1], parent)) {
union(costs[i][0], costs[i][1], parent);
answer += costs[i][2];
}
}
return answer;
}
public void union(int a, int b, int parent[]) {
int aParent = find(a, parent);
int bParent = find(b, parent);
if(aParent != bParent) {
parent[aParent] = bParent;
}
}
public int find(int i, int parent[]) {
if(parent[i] == i) {
return i;
} else {
return find(parent[i], parent);
}
}
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 여행경로 Java 풀이 및 해설 (0) | 2024.05.16 |
---|---|
[프로그래머스] 가장 먼 노드 Java 풀이 및 해설 (1) | 2024.05.15 |
[프로그래머스] 징검다리 건너기 Java 풀이 및 해설 (0) | 2024.05.14 |
[프로그래머스] 보석 쇼핑 Java 풀이 및 해설 (0) | 2024.05.13 |
[프로그래머스] 불량 사용자 Java 풀이 및 해설 (0) | 2024.05.11 |
Comments