[BOJ_1647] 도시 분할 계획 (골드 4) - JAVA

---

🐾 알고리즘

• 최소간선비용을 구하는 크루스칼 알고리즘
• 프림알고리즘으로도 구현 가능 (당연)

 

---

🐾 생각 포인트

• int 형을 넘어가는 값이 발생하므로 고려해서 구현할 것.
• 왜 아래와 같은 조건을 넣어서 문제를 구현하려 했을 때는 답은 나오는데, 97%에서 오류나는지 의문 (해결중 .. 2023-12-10 => 해결책을 알게되면 작성하겠음..!)

			if(pick == N - 2) {
            break;		
            }

 

• 마을을 2개로 분할하는 방법 중 유지비가 가장 많이 드는 길을 찾아내서 그 길을 제거하면 두개로 나눠진다는 점... 정말 신박하다. (다른 분 코드 참고함) 어떻게 이런 생각을 했지.

 

---

🐾 소스코드

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_1647 {
	static int[] parent;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); //정점의 개수 : 집의 개수
		int M = Integer.parseInt(st.nextToken()); //간선의 개수 : 길의 개수
		
		int[][] edges = new int[M][3];
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			edges[i][0] = Integer.parseInt(st.nextToken());
			edges[i][1] = Integer.parseInt(st.nextToken());
			edges[i][2] = Integer.parseInt(st.nextToken());
			
		}//입력완
		
		//두개의 집으로 분리해야함
		
		Arrays.sort(edges, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});
		
		parent = new int[N+1];
		for(int i=1;i<N+1;i++) {
			parent[i] = i;
		}
		
		long ans = 0;
		int pick = 0;
		int bigger = 0; //연결한 길 중 가장 큰 값 구해서 나중에 이길 제거하면 마을이 2개로 ㅈ쪼개짐.
		
		for(int i=0;i<M;i++) {
			int x = edges[i][0];
			int y = edges[i][1];
			
			if(findset(x) != findset(y)) {
				union(x, y);
				bigger = Math.max(edges[i][2], bigger); //길중 유지비가 가장 많이 드는 길 찾기
				ans += edges[i][2];
				pick++;
			}
//			if(pick == N - 2) {
//				break;
//			}
		}
		//길 중에서 bigger one 빼기 => 마을 두개로 분리하기
		System.out.println(ans - bigger);
		
		
		
	}
	private static void union(int x, int y) {
		parent[findset(y)] = findset(x);
	}
	private static int findset(int x) {
		if(x != parent[x])
			parent[x] = findset(parent[x]);
		return parent[x];
	}
}

---

😵‍💫 공부해야 할 점

• 한 문제를 풀더라도 여러 방면으로 풀어보려고 노력하자.
• 문제 맞는 것이 중요한게 아니고, 내가 진짜 스스로의 힘으로 구현할 수 있는지가 중요..