[프로그래머스] 섬 연결하기 (java)
🔗 문제링크
https://programmers.co.kr/learn/courses/30/lessons/42861
👩🏻💻 코드
import java.util.*;
class Edge implements Comparable<Edge> {
int s, e, cost;
Edge(int s, int e, int cost) {
this.s = s;
this.e = e;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
class Solution {
static int[] parent;
static PriorityQueue<Edge> edges;
public int solution(int n, int[][] costs) {
int answer = 0;
parent = new int[n];
edges = new PriorityQueue<>();
for (int i = 0; i < costs.length; i++) {
edges.add(new Edge(costs[i][0], costs[i][1], costs[i][2]));
}
for (int i = 0; i < n; i++) {
parent[i] = i;
}
while (!edges.isEmpty()) {
Edge cur = edges.poll();
if (find(cur.s) == find(cur.e)) {
continue;
}
union(cur.s, cur.e);
answer += cur.cost;
}
return answer;
}
public static int find(int x) {
if (parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]);
}
}
public static void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootY] = rootX;
}
}
📝 정리
union-find를 이용하면 되는 문제였다. 오랜만에 접했더니 또 낯설어졌다.
완전히 내 것으로 만들기 위해 노력해야겠다.
Author And Source
이 문제에 관하여([프로그래머스] 섬 연결하기 (java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hammii/프로그래머스-섬-연결하기-java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)