n๊ฐ์ ์ฌ ์ฌ์ด์ ๋ค๋ฆฌ๋ฅผ ๊ฑด์คํ๋ ๋น์ฉ(costs)์ด ์ฃผ์ด์ง ๋, ์ต์์ ๋น์ฉ์ผ๋ก ๋ชจ๋ ์ฌ์ด ์๋ก ํตํ ๊ฐ๋ฅํ๋๋ก ๋ง๋ค ๋ ํ์ํ ์ต์ ๋น์ฉ์ return ํ๋๋ก solution์ ์์ฑํ์ธ์.
๋ค๋ฆฌ๋ฅผ ์ฌ๋ฌ ๋ฒ ๊ฑด๋๋๋ผ๋, ๋๋ฌํ ์๋ง ์์ผ๋ฉด ํตํ ๊ฐ๋ฅํ๋ค๊ณ ๋ด ๋๋ค. ์๋ฅผ ๋ค์ด A ์ฌ๊ณผ B ์ฌ ์ฌ์ด์ ๋ค๋ฆฌ๊ฐ ์๊ณ , B ์ฌ๊ณผ C ์ฌ ์ฌ์ด์ ๋ค๋ฆฌ๊ฐ ์์ผ๋ฉด A ์ฌ๊ณผ C ์ฌ์ ์๋ก ํตํ ๊ฐ๋ฅํฉ๋๋ค.
**์ ํ์ฌํญ
์
์ถ๋ ฅ ์
n costs return
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
๐ก ์ต์๋ถํฐ ๊ฐ์ ์ฐ๊ฒฐ
๐ก ์ฌ์ดํด ์์ฑ X
๐ก ์ด์ด์ง ๋
ธ๋ ํ์
1) ์ต์๋ถํฐ priorityQueue๋ฅผ ์ด์ฉํด ์ ๋ ฌ
class Edge implements Comparable<Edge> {
int start, end, cost;
public Edge(int start, int end, int cost){
this.start = start;
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Edge o){
return this.cost - o.cost;
}
}
...
pq.offer(new Edge(costs[i][0],costs[i][1],costs[i][2]));
...
2) ์ฌ์ดํด ์์ฑ X
๋ถ๋ชจ ๋
ธ๋๊ฐ ์๋ก ๊ฐ์ผ๋ฉด X, ์ฌ๊ท๋ฅผ ์ด์ฉํด ๋ถ๋ชจ ๋
ธ๋ ์ฐพ์
...
if(find(e.start) == find(e.end)) continue;
...
public static int find(int p){
if(parent[p] == p) return p;
return parent[p] = find(parent[p]);
}
3) ์ด์ด์ง ๋ ธ๋ ํ์
public static void union(int a, int b){
int rootA = find(a);
int rootB = find(b);
if(rootA != rootB) parent[rootB] = rootA;
}
import java.util.*;
class Edge implements Comparable<Edge> {
int start, end, cost;
public Edge(int start, int end, int cost){
this.start = start;
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Edge o){
return this.cost - o.cost;
}
}
class Solution {
static int[] parent;
static PriorityQueue<Edge> pq;
public int solution(int n, int[][] costs) {
int answer = 0;
parent = new int[n];
pq = new PriorityQueue<Edge>();
for(int i=0; i<n; i++)
parent[i] = i;
for(int i=0; i<costs.length; i++){
pq.offer(new Edge(costs[i][0],costs[i][1],costs[i][2]));
}
while(!pq.isEmpty()){
Edge e = pq.poll();
if(find(e.start) == find(e.end)) continue;
else {
union(e.start, e.end);
answer+=e.cost;
}
}
return answer;
}
public static int find(int p){
if(parent[p] == p) return p;
return parent[p] = find(parent[p]);
}
public static void union(int a, int b){
int rootA = find(a);
int rootB = find(b);
if(rootA != rootB) parent[rootB] = rootA;
}
}
์ฑ๊ณต~