[BOJ_6497]전력난 (골드 4) - JAVA

---

🐾 알고리즘

• 크루스칼 알고리즘
• MST
• 분리집합 ( 서로소 집합)
• Union - find

 

---

🐾 생각 포인트

• 마지막 답을 도출할 때 total cost에서 최소 비용을 빼줘야 절약한 최대비용이 출력된다.
• 난 처음에 최대비용을 출력하라고 해서 크루스칼 알고리즘과는 반대로 간선을 정렬할 때 가중치를 내림차순으로 정렬했더니 오답이 도출되었다. 잘 생각해보니, 최소비용을 전체에서 빼줘야 한다.

 

---

🐾 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main_6497 {
	static int[] parent;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		out: while (true) {
			st = new StringTokenizer(br.readLine());// 집의 수 (정점)
			int m = Integer.parseInt(st.nextToken());// 길의 수(간선)
			int n = Integer.parseInt(st.nextToken());
			if (n == 0 && m == 0) {
				break out;
			}
			
			int[][] edges = new int[n][3];
			
			int total = 0;
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				edges[i][0] = Integer.parseInt(st.nextToken()); // from
				edges[i][1] = Integer.parseInt(st.nextToken()); // to
				edges[i][2] = Integer.parseInt(st.nextToken()); // 가중치
				total += edges[i][2];
			}

			Arrays.sort(edges, new Comparator<int[]>() {

				@Override
				public int compare(int[] o1, int[] o2) {
					return o1[2] - o2[2];
				}

			});

//			for (int[] e : edges) {
//				System.out.println("내림차순 : " + Arrays.toString(e));
//			}

			parent = new int[m+1];
			for (int i = 1; i < m+1; i++) {
				parent[i] = i;
			}

			int ans = 0;
			int pick = 0;

			for (int i = 0; i < n; i++) {
				int x = edges[i][0];
				int y = edges[i][1];

				if (findset(x) != findset(y)) {
					union(x, y);

					ans += edges[i][2];
//					System.out.println(ans);
					pick++;
				}
				if (pick == m - 1)
					break;
			}

			System.out.println(total - ans);

		} // while

	}

	private static void union(int x, int y) {
		parent[findset(y)] = findset(x);
	}

	private static int findset(int x) {
		if (x != parent[x])
			return parent[x] = findset(parent[x]);
		return x;
	}
}

 

---

😵‍💫 공부해야 할 점

• 알고리즘 원리를 잘 생각하면서 풀자!
• 단기 기억 금지.. 내것으로 만들기..