⭐ 문제링크
오늘은 알고리즘 시간에 배운 내용을 복습하고자 해당 문제를 가져왔습니다.
1. 문제요구
- 모든 노드는 포함되어야 한다.
- 1번의 가정 하에, 가장 작은 비용을 구하라.
- 사이클은 있어선 안된다.
2. 개념
참고해주세용
3. 코드
3-1) 첫 번째 시도
public class Main {
static class Vertex implements Comparable<Vertex> {
int from;
int to;
int cost;
public Vertex(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Vertex o) {
return this.cost-o.cost;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int vertexCount = Integer.parseInt(br.readLine());
int edgeCount = Integer.parseInt(br.readLine());
int []parent = new int[vertexCount+1];
for(int i=1; i<=vertexCount; i++){
parent[i] = i; //본인으로 부모 노드 초기화
}
PriorityQueue<Vertex> pq = new PriorityQueue<>();
for(int i=0; i<edgeCount; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
pq.add(new Vertex(from, to, cost));
}
edgeCount=0;
int answerCost=0;
while (edgeCount+1!=vertexCount) { // vertexCount = edge+1;
Vertex now = pq.poll(); // 1 0
if(parent[now.to]!=parent[now.from]) { //find 함수가 다르다.
int min = Math.min(parent[now.to], parent[now.from]);
parent[now.to] = min;
parent[now.from] = min;
edgeCount++;
answerCost+=now.cost;
}
}
System.out.println(answerCost);
}
}실패했습니다.
왜냐! 해당 문제는 방향성에 따라 루트 노드를 정해줬어야 하는데 나의 코드 같은 경우에는 그냥 작은 노드값을 기준으로 루트 노드를 선정해주었기 때문입니다.
즉 부모 노드에 대한 갱신이 제대로 이루어지고 있지 않아 해당 코드는 실패하게 되었습니다.
3-2) union&Find 자료구조
union(x, y)
x, y의 루트 노드를 찾고 다르면 y를 x의 자손으로 넣어 두 트리를 합한다.
-> 더 낮은 트리를 더 높은 트리의 자손으로 합칩니다.
시간 복잡도: O(N)보다 작으므로 find 연산이 전체 수행 시간이 지배한다.
find(x)
노드의 집합 번호는 루트 노드이므로, 루트 노드를 확인하여 같은 집합인지 확인한다.
시간 복잡도: 트리의 높이와 시간 복잡도가 동일하다. (최악: O(N-1))
3-2) 성공코드
public class Main {
static class Edge implements Comparable<Edge> {
int from;
int to;
int cost;
public Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int vertexCount = Integer.parseInt(br.readLine());
int edgeCount = Integer.parseInt(br.readLine());
parent = new int[vertexCount + 1];
for (int i = 1; i <= vertexCount; i++) {
parent[i] = i;
}
PriorityQueue<Edge> pq = new PriorityQueue<>();
for (int i = 0; i < edgeCount; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
pq.add(new Edge(from, to, cost));
}
int totalCost = 0;
int edgesUsed = 0;
while (!pq.isEmpty() && edgesUsed < vertexCount - 1) {
Edge now = pq.poll();
if (find(now.from) != find(now.to)) {
union(now.from, now.to);
totalCost += now.cost;
edgesUsed++;
}
}
System.out.println(totalCost);
}
static int find(int x) {
if (parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]);
}
}
static void union(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
parent[x] = y;
}
}
}
3. 결과
끄끄
