[백준] 1368: 물대기 - 최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) JAVA

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

1368번: 물대기

풀이

일반적인 크루스칼 문제입니다.

다만, 지금까지는 노드의 상태에 따라서 연결을 할지 말지 결정했다면,

이번에는 노드의 비용까지 고려해야하는 점이 다른 점입니다.

 

이 문제를 풀다보면, 그래프가 2가지 그래프가 나와야한다는 것을 알 수있습니다.

첫번째는, 일반 간선을 연결한 노드

두번째는, 우물을 파는데 드는 비용

 

그렇기에 하나의 그래프로 합쳐서 진행해야 계산이 가능합니다.

그러기 위해 일반간선을 연결한 노드에다가 가상 노드를 추가하여 우물을 파는데 드는 비용을 저장합니다.

이때 가상노드의 인덱스는 0으로 설정하고, 진행합니다.

 

이 문제같은경우, 입력값에 보면 자기 자신으로 향하는 노드의 비용은 0 입니다.

이걸 i == j 일떄, 즉 자신으로 향할때 본인 노드를 하나의 간선으로 다시 추가해줍니다.

그렇게하면 노드 0 이 추가되는데, 어처피 그래프로써 연결이 다 된다면, 해당 그래프의 비용도 자동으로 추가되므로 성공적으로 일반간선에 우물을 파는데 드는 비용을 연결한 것 입니다.

 

[이떄 드는 의문은, 가상 노드를 연결한다고해서 해당 우물의 비용이 연결되는 것인가?] 라는 의문이 생깁니다.

대답은 그렇습니다.

이유는 사실상 하나의 우물만 파놓으면, 모든 노드가 그 우물에서 물을 다 퍼올 수 있기에 최소한의 비용이 드는 우물값을 Collections.sort로 오름차순 연결되기에 자동으로 최소비용으로 모든 노드를 가져올 수 있습니다.

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

 

코드

import java.util.*;



public class Main {
	public static int N;
	public static int[] parent = new int[301];
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static int[] nodesCost = new int[301];
	public static int result = 0;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	
    	for(int i=1; i<=N;i++) {
    		parent[i] = i;
    	}
    	for(int i=1;i<=N;i++) {
    		nodesCost[i] = sc.nextInt();
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=N;j++) {
    			int cost = sc.nextInt();
    			if( i == j) {
    				edges.add(new Edge(0, j, nodesCost[i]));	
    			}
    			else if( i < j) { //전체 다 넣어도 어처피 findParent에서 같으면 걸러지기에 상관은 없지만, 최적화 
    				edges.add(new Edge(i, j, cost));	
    			}
    		}
    	}
    	
    	Collections.sort(edges);
    	
    	for(int i=0;i<edges.size();i++) {
    		int nodeA = edges.get(i).nodeA;
    		int nodeB = edges.get(i).nodeB;
    		int cost = edges.get(i).distance;
    		if( findParent(nodeA) != findParent(nodeB) ) {
    			unionParent(nodeA, nodeB);
    			result += cost;
    		}
    	}
    	System.out.println(result);
    	
    }
    
    public static int findParent(int x) {
    	if( x == parent[x]) return x;
    	return parent[x] = findParent(parent[x]);
    }
    
    
    public static void unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	if( a < b) parent[b] = a;
    	else parent[a] = b;
    	
    }
    
}

class Edge implements Comparable<Edge>{
	int nodeA;
	int nodeB;
	int distance;
	public Edge(int nodeA, int nodeB, int distance) {
		this.nodeA = nodeA;
		this.nodeB = nodeB;
		this.distance = distance;
	}
	
	@Override
	public int compareTo(Edge other) {
		if(this.distance < other.distance) {
			return -1;
		}else if(this.distance > other.distance) {
			return 1;
		}else {
			return 0;
		}
	}
}