BOJ 1922 네트워크 연결

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

최소신장트리를 사용해서 풀이하였다.
최소신장트리MST가 궁금하다면?

풀이방법은 Prim 알고리즘 사용과 Kruscal 알고리즘을 사용할 수있다.(위의 링크 참고)

Prim 알고리즘 사용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static int[][] line;
	private static boolean[] visited;
	private static int N;
	private static int totalCost = 0;	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		line = new int[N+1][N+1];
		visited = new boolean[N+1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			
			if(line[start][end]==0) {
				line[start][end] = val;
				line[end][start] = val;
			}else {
				int newVal = Math.min(line[start][end], val);
				line[start][end] = newVal;
				line[end][start] = newVal;
			}
		}
		
		prim(1); //프림 알고리즘 사용
		System.out.println(totalCost);
	}
	private static void prim(int select) {
		visited[select] = true;
		int nextSelect = -1;
		int nextCost = 200000;
		for (int i = 1; i <= N; i++) { // 방문한 점을 선택
			if(!visited[i]) continue;
			for (int j = 1; j <= N; j++) { // 미방문 점을 선택
				if(!visited[j] && line[i][j]!=0 && line[i][j]< nextCost) {
					nextSelect = j;
					nextCost = line[i][j];
				}
			}
		}
		if(nextSelect==-1) return;
		totalCost+= nextCost;
		prim(nextSelect);
	}

}

Kruscal 알고리즘 사용

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

public class Main{
	static class Node implements Comparable<Node>{
		int start;
		int end;
		int val;
		public Node(int start, int end, int val) {
			this.start = start;
			this.end = end;
			this.val = val;
		}
		@Override
		public int compareTo(Node o) {
			return this.val - o.val;
		}
		
	}
	
	private static int N,M;
	private static int[] parents;
	private static Node[] line;
	private static int lineCnt = 0;
	private static int totalCost = 0;
	
	// 크기가 1인 단위집합 만들기
	static void make() {
		for (int i = 1; i <= N; i++) {
			parents[i] = i;
		}
	}
	// parent 찾기
	static int findSet(int a) {
		if(parents[a]==a) return a;
		return parents[a] = findSet(parents[a]);
	}
	// union
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		
		if(aRoot == bRoot) return false;
		if(aRoot < bRoot) parents[bRoot] = aRoot;
		else parents[aRoot] = bRoot;
		return true;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		parents = new int[N+1];
		line = new Node[M];
		// 간선리스트 세팅
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			line[i] = new Node(start, end, val);
		}
		// Kruscal 알고리즘 사용
		// 1. 간선 리스트 오름차순 정렬
		Arrays.sort(line);
		// 2. 단위집합 세팅
		make();
		
		for (Node node : line) {
			if(union(node.start, node.end)) {
				totalCost += node.val;
				if(++lineCnt == N-1) break;
			}
		}
		System.out.println(totalCost);
	}


}

Prim 적용시 걸리는 시간이 Kruscal 사용시보다 2배 더 걸리는 것을 알 수 있다.

=> Prim은 정점에 비해 간선이 많은 밀집그래프에서, Kruscal은 정점에 비해 간선이 적은 희소그래프에서 유리하다!