[BOJ] 백준 1414번 불우이웃돕기 (Java)

#1414 불우이웃돕기

난이도 : 골드 2

유형 : 문자열 / MST / 크루스칼 

 

1414번: 불우이웃돕기

▸ 문제

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.

다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

▸ 출력

첫째 줄에 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력한다. 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.

 

문제 풀이  

최대의 랜선 길이를 기부하기 위해서는 집에 있는 모든 컴퓨터를 최소의 랜선 길이로 연결시켜주면 된다. 그러므로 최소 스패닝 트리 MST 알고리즘을 사용해야 한다. MST 알고리즘 유형으로 대표적으로 프림과 크루스칼이 있는데 프림은 정점 위주의 탐색이고 크루스칼은 간선 위주의 탐색이다.

 

	크루스칼 알고리즘	프림 알고리즘
탐색 방법	간선 위주	정점 위주
탐색 과정	시작점 따로 지정없이 최소 비용의 간선을 차례대로 대입하면서 사이클이 이루어지기 전까지 탐색	시작점을 지정한 후 가까운 정점을 선택하면서 모든 정점을 탐색
사용	간선의 개수가 적은 경우 크루스칼 알고리즘이 용이	간선의 개수가 많은 경우에는 정점 위주 탐색인 프림이 용이
시간복잡도	O(ElogV)	O(ElogV)

 

크루스칼 알고리즘 사용

해당 문제는 i와 j를 잇는 랜선 길이로 값을 주어졌기 때문에 간선 위주로 탐색하는 것이 용이하다. 모든 간선에 대한 정보를 우선순위 큐에 넣어주고 싸이클이 발생하지 않는 모든 간선을 최소 비용 순대로 연결시켜주면 된다. 싸이클에 대한 여부는 간선이 포함될 때 마다 연결된 정점을 카운트하여 해당 갯수가 총 정점 갯수와 같은지로 판단해준다. 

int size = pq.size();
int cycleNode = 1;
int result = 0;
for(int i=0; i<size; i++) {
	Node node = pq.poll();
	int rx = find(node.to);
	int ry = find(node.from);
	
	if(rx != ry) {
		cycleNode++; 
		result += node.value;
		union(node.to, node.from);
	}
}

if(cycleNode != n) { // 싸이클 그래프에 연결된 정점이 모든 정점을 포함하지 않을 경우 
	System.out.println(-1);
}else {
	System.out.println(total-result);	
}

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main{

	static class Node implements Comparable<Node>{
		int to;
		int from;
		int value;
		public Node(int to, int from, int value) {
			this.to = to;
			this.from = from;
			this.value = value;
		}
		@Override
		public int compareTo(Node o) {
		return this.value - o.value;
		}
	}
	static int n;
	static int[] parents;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		char[][] map = new char[n][n];
		for(int i=0; i<n; i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		parents = new int[n+1];
		for(int i=1; i<=n; i++) {
			parents[i] = i;
		}
		
		int total = 0;
		Queue<Node> pq = new PriorityQueue<>();
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if('a' <= map[i][j] && map[i][j] <= 'z') {
					total += map[i][j]-96;
					pq.add(new Node(i+1,j+1, map[i][j]-96));
				}else if('A' <= map[i][j] && map[i][j] <= 'Z') {
					total += map[i][j]-38;
					pq.add(new Node(i+1,j+1, map[i][j]-38));
				}
			}
		}
		
		int size = pq.size();
		int cycleNode = 1;
		int result = 0;
		for(int i=0; i<size; i++) {
			Node node = pq.poll();
			int rx = find(node.to);
			int ry = find(node.from);
			
			if(rx != ry) {
				cycleNode++;
				result += node.value;
				union(node.to, node.from);
			}
		}
		if(cycleNode != n) {
			System.out.println(-1);
		}else {
			System.out.println(total-result);	
		}
	}
	
	static int find(int x) { 
		if (parents[x] == x) { 
			return x; 
	     } 
		return parents[x] = find(parents[x]);
	} 
	     
	static void union(int x, int y) {
		x = find(x); 
		y = find(y); 
	    if (x < y) { 
	    	parents[y] = x; 
	    } 
	    else { 
	    	parents[x] = y; 
	    } 
	}	
}