[JAVA] BOJ(백준) - 네트워크 연결 - 1922

문제내용

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

1922번: 네트워크 연결

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

---

문제 접근 방법

각 컴퓨터를 연결시키고 최소비용을 구하는 문제이다. 이때 컴퓨터간의 연결은 사이클이 안돌아도 되는 조건이기 때문에 MST에 관한 문제라고 볼 수 있다.

따라서 해당 문제를 풀기위해 크루스칼 알고리즘, 프림 알고리즘 중 하나를 택해 풀어 낼수있는데 본인은 크루스칼 알고리즘을 선택하여 풀었다.

 

MST와 각 알고리즘에 대한 자세한 설명은 아래 블로그에 나와있다.

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

 

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

 

이문제를 크루스칼 알고리즘으로 풀기위해선 아래와같은 단계가 필요하다.

크루스칼 풀이 과정

1. 간선과 비용
   크루스칼 알고리즘은 기본적으로 간선의 가중치를 보고 최소의 가중치를 갖는 간선을 하나씩 차례대로 선택해서 신장트리를 만드는 알고리즘이다. 따라서 간선에 연결된 정점 두개와 간선의 가중치를 저장해줄 공간이 필요하다.
   여기서 나는 리스트를 이용했고 제네릭에는 정점 두개와 간선의 가중치를 넣어줄 수 있는 클래스를 만들어 넣어줬따.
2. 정렬
   최소비용으로 간선을 연결해야하기 때문에 간선의 가중치를 기준으로 리스트를 오름차순 정렬해준다.
   오름차순정렬 해주는 이유는 1번에서 말했던것 처럼 최소의 가중치를 갖는 간선을 차례대로 선택하기 위해서이다.
   
   
3. 사이클 판단
   MST는 최소 신장 트리 즉, 사이클이 발생하면 안되는 트리이다.
   따라서 간선을 선택하는 과정에서 선택한 간선이 이전에 선택한 간선들에 의해 사이클이 발생하는지 안하는지 판단하는 로직이 필요하다.
   이에대한 로직은 Union-Find 알고리즘을 이용해 판단한다.
   
   
4. Union-Find
   Union-Find 알고리즘을 이용한다면 사이클이 발생하는지 안하는지 알수 있다.
   원리는 만약 선택한 간선을 이루는 정점 두개가 같은 루트노드를 갖고 있다면 이 간선을 추가할때 사이클이 발생하게 된다.
   따라서 선택한 간선을 이루는 정점 두개는 항상 다른 루트 노드를 갖고 있어야하고 다른 루트 노드를 갖을때 Union메서드를 이용해 트리를 합쳐주는 과정이 필요하다.
   (참고. Union-Find : https://record-developer.tistory.com/86 )

1~4번 과정을 반복해서 MST 트리를 만들면서 선택한 간선들의 가중치 합을 구하면되는 문제이다.

자세한 내용은 아래 코드를 보자.

---

풀이

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

public class Main {
	static int answer = 0; //최소비용
	static int[] parents; //parents[자식노드] = 부모노드
	static ArrayList<Node1922> list = new ArrayList<Node1922>(); //간선과 비용 표시리스트
	static class Node1922{ //연결된 정점2개와 간선의 가중치 나타내는 클래스
		int node1;
		int node2;
		int nodeCost;
		
		public Node1922(int node1, int node2, int nodeCost) {
			this.nodeCost = nodeCost;
			this.node1 = node1;
			this.node2 = node2;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine()); //정점개수
		int m = Integer.parseInt(br.readLine()); //간선개수
		parents = new int[n+1];
		
		//parents배열 초기화
		for(int i=1; i<=n; i++)
			parents[i] = i;
		
		//간선에 연결된 정점 2개랑 가중치 넣기
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			list.add(new Node1922(v1, v2, c));
		}
		
		kruskal(n);//크루스칼 알고리즘
		System.out.println(answer);//출력
	}
	
	//크루스칼 알고리즘
	public static void kruskal(int n) {
		listSort(); //list 가중치 기준으로 오름차순 정렬
		int cnt = 0; //선택된 간선 개수
		
		//간선 순회
		for(int i=0; i<list.size(); i++) {
			int v1 = list.get(i).node1;
			int v2 = list.get(i).node2;
			int c = list.get(i).nodeCost;
			
			//간선의 개수가 정점개수-1 이면 종료.
			if(n-1==cnt) return;
			
			//사이클이되는지 안되는지 판단
			if(!sameP(v1,v2)) {
				union(v1,v2);//다른루트 노드 = 사이클 x = 트리 합치기
				answer += c;//선택한 간선의 가중치 더하기
				cnt++;//간선 개수 증가
			}
		}
		
	}
	
	public static void listSort() {
		Collections.sort(list, new Comparator<Node1922>() {

			@Override
			public int compare(Node1922 o1, Node1922 o2) {
				int c1 = o1.nodeCost;
				int c2 = o2.nodeCost;
				
				if(c1<c2) return -1;
				else if(c1>c2) return 1;
				else return 0;
			}
		});
	}
	
	public static void union(int v1, int v2) {
		v1 = find(v1);
		v2 = find(v2);
		
		if(v1>v2) parents[v1] = v2;
		else if(v1<v2) parents[v2] = v1;
	}
	
	public static boolean sameP(int v1, int v2) {
		v1 = find(v1);
		v2 = find(v2);
		
		if(v1!=v2) return false;
		return true;
	}
	
	public static int find(int v) {
		if(parents[v]==v) return v;
		
		return parents[v] = find(parents[v]);
	}
}

 

---

마치며

MST를 만드는 알고리즘에는 크루스칼 뿐만아니라 프림 알고리즘도 존재한다.

해당 문제를 프림 알고리즘으로도 풀어보는 연습을 하는게 좋을듯하다.

참고로
크루스칼 알고리즘은 간선의 개수가 적은 희소그래프에서 유리하다고 하고
프림 알고리즘은 정점을 기준으로 하기 때문에 간선의 개수가 많은 밀집그래프에서 유리하다고 한다.