[JAVA] 백준 1922 문제 - 네트워크 연결

백준 알고리즘 문제 1922 문제를 정리하는 포스팅입니다. 최적의 코드가 아니니 해당 코드는 참고만 하시기 바랍니다.

1. 최소신장트리 ( Minimum Spanning Tree )

 

이 문제는 최소 신장 트리 문제입니다. 최소 신장 트리(MST)는 그래프 알고리즘 중 하나 입니다.

최소 신장 트리(MST)는 Kruskal 알고리즘과 Prim 알고리즘이 있습니다.

이 문제는 Kruskal 알고리즘 문제로 다음과 같이 생각해볼 수 있습니다.

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클이 생기지 않는 간선을 선택합니다.
   - 비용이 낮은 순서로 간선을 선택합니다.
   - 사이클이 생성되지 않는다 함은 노드-1개의 간선을 선택한다는 의미 입니다.
3. 선택된 간선을 현재 MST의 집합에 추가한다.

2. 코드

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

public class Main {

	private static int N, M;
	private static final int FROM = 0, TO = 1, COST = 2;
	private static ArrayList<Integer[]> edges;
	private static StringTokenizer st;
	private static int[] union;
	
	public static void main(String[] args) throws IOException {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		edges = new ArrayList<>();
		union = new int[N+1];
		
		for(int i=1; i<N+1; i++) union[i] = i;
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			Integer[] temp = new Integer[3];
			temp[FROM] = Integer.parseInt(st.nextToken());
			temp[TO] = Integer.parseInt(st.nextToken());
			temp[COST] = Integer.parseInt(st.nextToken());			
			edges.add(temp);
		}
		
		edges.sort(new Comparator<Integer[]>() {
			@Override
			public int compare(Integer[] o1, Integer[] o2) {
				// TODO Auto-generated method stub
				return o1[COST] < o2[COST] ? -1 : 1;
			}
		});
		
		int select = 0, cost_sum = 0;
		for(int i=0; i<M; i++) {
			Integer[] edge = edges.get(i);
			if(union(edge[FROM], edge[TO])) {
				select++;
				cost_sum += edge[COST];
			}
			if(select == N-1) {
				break;
			}
		}
		System.out.println(cost_sum);
				
	}
	
	private static boolean union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a == b) return false;
		union[b] = a;
		return true;
	}
		
	private static int find(int a) {
		if(a == union[a]) return a;		
		return union[a] = find(union[a]);
	}	
}

전체 코드를 부분적으로 나눠 설명 드리겠습니다.

<< 정렬 코드 >>

for(int i=0; i<M; i++) {
	st = new StringTokenizer(br.readLine());
	Integer[] temp = new Integer[3];
	temp[FROM] = Integer.parseInt(st.nextToken());
	temp[TO] = Integer.parseInt(st.nextToken());
	temp[COST] = Integer.parseInt(st.nextToken());			
	edges.add(temp);
}

edges.sort(new Comparator<Integer[]>() {
	@Override
	public int compare(Integer[] o1, Integer[] o2) {
		// TODO Auto-generated method stub
		return o1[COST] < o2[COST] ? -1 : 1;
	}
});

 주어진 엣지가 모두 처음에 제공되기 때문에 해당 엣지들을 모두 입력 받아 비용에 따라 오름차순으로 정렬하는 것이 중요합니다.

private static boolean union(int a, int b) {
	a = find(a);
	b = find(b);
	if(a == b) return false;
	union[b] = a;
	return true;
}


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

 정렬이 되었다면 해당 엣지를 가지고 유니온 파인드를 수행하여 최소 비용으로 모든 노드들이 이어지는지 확인해줍니다. 선택된 엣지가 노드의 -1 한 만큼 선택되었다면 선택된 엣지들로 구성된 트리가 완성되었다고 판단하면 됩니다.

 이 문제는 최소 신장 트리의 가장 기본이 되는 문제 같습니다. 이 문제를 이해하고 다른 문제를 심화적으로 연습해보면 이해가 빠를 것 같네요!!