[BaekJoon] 1647 도시 분할 계획 (Java)

SeongWon Oh·2021년 11월 1일
0
post-thumbnail

🔗 문제 링크

https://www.acmicpc.net/problem/1647


📝 문제 설명

이번 문제는 간단한 MST문제로 모든 집들을 연결하는 최소 신장트리를 생성한 후 연결된 edge들 중에서 길이가 가장 긴 edge를 잘라 두개의 마을을 만들면 되는 문제이다.

저는 문제 풀이를 Kruskal's algorithm으로 풀이하였으며 코드는 아래와 같습니다.


👨🏻‍💻 작성한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	static int N; // 집의 개수
	static int M; // 길의 개수
	static ArrayList<Edge> edgeList = new ArrayList<>();
 	static int[] parent;
 	static int result = 0;
 	static int lastConnect; // 마지막으로 연결된 길의 weight저장
 	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		parent = new int[N+1];
		for (int i=1; i<=N; i++) parent[i] = i;
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			edgeList.add(new Edge(A, B, C));
		}
		
		Collections.sort(edgeList);
		
		kruskal();
		result -= lastConnect;
		System.out.println(result);
		
	}
	
	static void kruskal() {
		for (Edge e: edgeList) {
			union(e);
		}
	}
	
	
	static int find(int nodeId) {
		if (parent[nodeId] == nodeId) return nodeId;
		else return parent[nodeId] = find(parent[nodeId]);
	}
	
	static void union(Edge e) {
		int node1 = find(e.node1);
		int node2 = find(e.node2);
		if (node1 != node2) {
			result += e.weight;
			lastConnect = e.weight;
			parent[node1] = node2;
		}
	}
	
	
	
	static class Edge implements Comparable<Edge> {
		int node1;
		int node2;
		int weight;
		
		public Edge(int node1, int node2, int weight) {
			this.node1 = node1;
			this.node2 = node2;
			this.weight = weight;
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.weight-o.weight;
		}
	}

}

🚨compareTo 주의할 점
이전까지 comapareTo를 override할 때는 아래의 코드와 같이 작성하였다. 하지만 이러한 경우 두개의 값이 같아서 0을 return하는 경우가 없게 되어 위의 문제를 풀 때 런타임 에러가 발생하였었다.

		@Override
		public int compareTo(Edge o) {
			return this.weight < o.weight ? -1:1;
		}

그래서 다음부터 compareTo를 재정의 할 때는 아래와 같이 해당 값들을 뺀 값을 return하도록 해주자~!!!

		@Override
		public int compareTo(Edge o) {
			return this.weight-o.weight;
		}
profile
블로그 이전했습니다. -> https://seongwon.dev/

0개의 댓글