[이것이 코딩 테스트다] 어두운 길

문제

문제의 저작권은 ‘이것이 코딩테스트다’ 교재에 있습니다.

한 마을은 N개의 집과 M개의 도로로 구성되어 있다. 각 집은 0~N-1번까지의 번호로 구분된다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일하다. 예를 들어, 2번과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 가정하자. 하루 동안 이 가로등을 켜기 위한 비용은 7이 된다.

정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 한다. 결과적으로 일부 가로등을 비활성하여 최대한 많은 금액을 절약하고자 한다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성해라.

입력조건

• 첫째 줄에 집의 수 N( 1<= N <= 200,000)과 도로의 수 M(N-1 <= M <= 200,000)이 주어진다.

• 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X,Y,Z가 주어지며 공백으로 구분된다.(0 <= X,Y <= N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미이다. 단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이 합은 231보다 작다.

출력조건

첫째 줄에 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력한다.

테스트케이스

입력

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11

출력

51

접근방식

간선이 작은 노드들로 모든 노드를 연결시키고 남은 간선의 가중치 합을 계산하면 되는 문제이다. 크루스칼 알고리즘을 사용해서 풀었다.

1) 간선리스트에 간선정보(출발,도착,가중치)를 담는다.

2) parents배열에 자기자신을 집합으로 자기 번호를 넣는다.

3) 초기 세팅이 끝나면 간선을 오름차순으로 정렬하고 간선리스트에서 가중치가 가장 작은 간선을 먼저 꺼내서 Union-Find로 이 간선을 연결시킬지 판단한다.

• union(int a, int b) 함수에서 넘겨받은 from, to의 최상위 노드를 find()에서 구해서 부모노드가 같으면 사이클이 발생하므로 연결할 수 없기 때문에 return false 해준다. 두 부모노드가 다르면 더 작은값으로 갱신해준다.
• find(int a)에서는 a의 최상위 노드를 찾아 return한다. 자기자신이 집합인 노드가 최상위노드이므로 이때 return한다.

4) union(int a, int b)의 결과가 false이면 이 간선은 탈락이므로 Ans에 누적합해준다.

import java.io.*;
import java.util.*;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[] parents; // 각 노드의 부모노드 저장
	static int N, M; // 정점수, 간선수
	static ArrayList<Edge> edgeList; // 간선리스트
	static int Ans;

	static class Edge implements Comparable<Edge> {
		int from;
		int to;
		int w;

		public Edge(int from, int to, int w) {
			this.from = from;
			this.to = to;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.w, o.w);
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		parents = new int[N];
		edgeList = new ArrayList<>();

		// 1. 간선정보 입력
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int f = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			edgeList.add(new Edge(f, t, w));
		}

		// 2. 간선 오름차순 정렬
		Collections.sort(edgeList);

		// 3. 자기자신을 집합으로 한다.
		for (int i = 0; i < N; i++) parents[i] = i;

		// 4. 연결된 노드들을 합친다.
		for (Edge e : edgeList) {
			if (!union(e.from, e.to)) Ans += e.w; //연결못하는 노드들의 가중치를 합해줌
		}
		
		System.out.println(Ans);
	}

	public static boolean union(int a, int b) {
		a = find(a); // 5. 각 노드의 최상위 노드 찾기
		b = find(b);
		if (a == b) return false; // 부모노드가 같음 => 사이클 발생
		
		if (a < b)parents[b] = a;
		else parents[a] = b;
		return true;
	}

	private static int find(int a) {
		if (parents[a] == a) return parents[a];
		else return parents[a] = find(parents[a]);
	}
}