[Java] 백준 1414 불우이웃돕기 952hi의 접근방법

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

1414번: 불우이웃돕기

---

 

1. 접근방법

처음 설명을 읽을때 이해가안돼서 이해안된상태로 시작하는게 아닌 충분히 이해가 될때까지 문제만 읽었다. 문제를 읽으면서 가장 최소 랜선의 길이를 구하고 각 컴퓨터가 모두 연결을 시켜야 한다는 점에서 MST 

최소신장트리 알고리즘이 생각이 났다.

결론적으로는 크루스칼과 프림 둘중 하나를 선택해서 구현해야했다.

 

나는 크루스칼을 선택해서 사용했는데 

프림은 간선이 많을때 이득이라고 생각했다 정점이 최대 50개 뿐이고 최대 간선은 약 2500개라고 생각해

크루스칼이 좀 더 효율적이라고 생각했다. 간단하게 크루스칼을 설명하자면

 

예제1 입력을 예시로 설명하겠다.

주어진간선 정보에서 나자신을 향하는 간선을 제외하면 아래 그림과 같다.

간선을 제외하기전 0을 제외한 모든 a~Z으로 표시된 모든 간선의 가중치 합을 구한다 -> 1~9까지의합 45 

이 상태에서 모든 간선을 정렬하여 가장 작은 간선부터 차례로 선택해 사이클 발생여부와 가중치의 합을 구한다.

 

2~8까지 간선중 2가 가장 작으므로 선택하고 두 정점의 사이클여부를 확인해 사이클이 발생하지않는다면 두정점을 하나의 그룹 표시하고 간선의 합을 저장한다.

그 후 두 번째로 작은 가중치를 가진 간선을 선택하고 사이클 여부, 가중치 합산을 수행한다.

결과로 모든 정점이 하나의 그룹에 들어왔고 총 5의 가중치의 합 즉 랜선 5만큼 길이로 모든 컴퓨터를 연결할 수 있게되고 총 45의 길이의 랜선중 5만 사용했으므로 40만큼 기부를 할 수 있게 된다. 

 

2. 실수 및 느낀점

 

정점이 1개 즉 컴퓨터가 하나있을때를 생각해주지 않아서 한번에 통과하지 못했다.

하나만 있을때는 그냥 연결하지않아도 되기때문에 모든 랜선을 기부할 수 있다.

if(n==1) res = cable; << 처럼 1이면 바로 길이를 주고 출력할 수 있도록 코드를 구현해 맟출 수 있었다.

 

매번 틀리는 유형이 1이나 제일큰 N일때 많이 발생한다고 생각이 들어서 

구현전에 미리 엣지 케이스에 대해 생각을 하면 더 효율적인 코드를 생각할 수 있다고 느꼇다.

 

3. 코드

import java.io.*;
import java.util.*;
public class boj1414 {
	static int p[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<int[]> q = new PriorityQueue<>((o1,o2)->o1[2]-o2[2]);
		int cnt=0,res=-1;
		int a = 0;
		int cable = 0;
		p = new int[n+1];
		for(int i=1;i<n+1;i++) p[i]=i;
		String temp;
		for(int i=0;i<n;i++) {
			temp = br.readLine();
			for(int j=0;j<n;j++) {
				a = temp.charAt(j)-0;
				if(a>=97) a-= 96;
				else a -=38;
				if(temp.charAt(j)=='0') continue;
				cable += a;
				if(i==j) continue;
				q.offer(new int[]{i,j,a});
			}
		}
		a=0;
		if(!q.isEmpty()) {
			int[] comp;
			while(!q.isEmpty()) {
				comp = q.poll();
				if(unionp(comp[0],comp[1])) {
					cnt++;
					a+=comp[2];
				}
				if(cnt==n-1) {
					res = cable - a;
					break;
				}
			}
		}
		if(n==1) res = cable;
		System.out.println(res);
	}
	private static boolean unionp(int i, int j) {
		i = findp(i);
		j = findp(j);
		if(i==j) return false;
		if(i>j) p[i]= j;
		else p[j] = i;
		return true;
	}
	private static int findp(int x) {
		if(p[x]==x) return x;
		return p[x]=findp(p[x]);
	}
}