원더랜드(최소스패닝트리 문제 - 크루스칼 알고리즘)

설명

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지 보수하는 재정이 바닥난 것이다.

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

아래의 그림은 그 한 예를 설명하는 그림이다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

 

입력

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.

 

출력

모든 도시를 연결하면서 드는 최소비용을 출려한다.

예시 입력 1 

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

예시 출력 1

196

 

수도 코드

우선 직전 문제에서 사용했던 거와 같이 서로소 집합을 Union&Find알고리즘으로 구현해보도록 하겠습니다.

요소들을 같은 집합끼리 묶고 난 후 그 집합을 연결하는 최소비용 다리를 하나 구해서 합하는 식으로 진행하려 합니다.

import java.util.Scanner;

public class Wonder {
	static int[] arr;
	public static int Find(int v) {
		if(v == arr[v]) return v;
		else return arr[v] = Find(arr[v]);
	}
	
	public static int Union(int a, int b, int c) { // 리턴타입 int에러
		int fa = Find(a);
		int fb = Find(b);
		if(fa != fb) arr[fa] = fb;
		if(fa == fb) return c;
	}

	public static void main(String[] args) {
		// 입력
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		arr = new int[n+1];
		for(int i=0; i<=n; i++) arr[i] = i;
		for(int i=0; i<=m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			Union(a,b,c);
		}
		// 누적 이슈 존재

	}

}

이렇게 작성했을 때 두 가지 의문점이 생겼습니다.

 

1.

Union( ) 리턴 타입을 int로 주고 return값 또한 int로 주었음에도 

This method must return a result of type int 에러가 발생했습니다.

혹시 리턴 타입이 항상 void인지 확인 필요했습니다.

-> 

Union(a, b, c) 메서드는 int를 리턴하니까 int k = Union(a, b, c)와 같이 호출해야 하고

Union 메서드가 if 조건에 따라 리턴을 할 수 도 있고 안할 수 도 있게 작성했는데 항상 리턴하도록 만들어 주었어야 했습니다.

 

 

2.

main메서드 하단에 결과를 반환해야 할 것 같은데 어떤 형태로 작성해야 할까 고민이 되었습니다.

 

 

---

 

 

대략적인 코드는 떠오르는데, 2번에서 고민했던 것처럼 main메서드 하단에 어떤 식으로 출력해야 하는지 궁금해졌습니다. 강의를 통해 어떤 알고리즘을 써서 어떻게 구현했는지 제가 이해한 것을 토대로 그림을 그려가며 말씀드려보겠습니다.

 

 

---

 

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로.

최소 비용 신장 트리(Minimum Spanning Tree)를 만드는 대표적인 알고리즘이기도 합니다.

   노드 = 정점 : 그래프에서 동그라미 부분

   간선 = 거리 = 비용 : 그래프에서 선에 해당하는 부분

 

순서: 

모든 노드를 최대한 적은 비용으로 연결시키면 되므로

우선 cost를 오름차순으로 정렬한 뒤 비용이 적은 간선부터 트리에 포함시킵니다.

여기서 회로가 되면 안 되므로 이때 Find & Union 알고리즘을 적용합니다.

 

이와 같이 크루스칼 알고리즘은 정렬 알고리즘과 Find & Union 알고리즘의 합이라고 말할 수 있습니다. 

시간 복잡도는 O(E log E)인데 그 이유는 모든 간선(E)을 가중치 기준으로 오름차순 정렬하므로 간선의 개수만큼 시간 복잡도가 계산되기 때문입니다.

    E개의 데이터를 정렬했을 때의 시간 복잡도는 O(ElogE)

 

 

---

​

이전 코테 문제에서 여러 번 구현해봤지만 생각을 못했던 부분은 

1. 간선 정보를 객체로 저장

2. 객체 저장할 arr생성  

 

💡 여러 정보가 주어질 때 객체로 저장할 수 있는지, 이때 배열이 쓰일지 항상 생각하는 습관을 가집시다!

 

 

그리고

Union&Find 알고리즘 코드를 전 문제를 풀면서 암기했었는데 이제 보니 정작 이걸 왜 사용하는지까지 완전한 이해는 부족했던 것 같습니다. 간단하게 정리해서 외워두도록 하겠습니다!

 

 

💡

Union&Find 알고리즘으로 문제를 푼 이전 글을 먼저 보고 오시면 더 좋습니다.

[코딩 테스트(JAVA)/인프런 문제] - 친구인가? (Disjoint-Set : Union&Find)

    Find( ) : 집합 번호 출력

    Union( ) :  같은 집합 처리 

import java.util.*;
class Main {
	
	public static int Find(int v){
		if(v==arr[v]) return v;
		else return arr[v]=Find(arr[v]);
	}
    
	public static void Union(int a, int b){
		int fa=Find(a);
		int fb=Find(b);
		if(fa!=fb) arr[fa]=fb;
	}
    
	public static void main(String[] args){
		.......
	}
    
}

 

 

코드 구현 & 실패 코드

package ch09;

import java.util.*;

class Edge implements Comparable<Edge> { 
	public int v1;
	public int v2;
	public int cost;
	
	
	Edge(int v1, int v2, int cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}
	
	
	@Override
	public int compareTo(Edge e) {
		return this.cost - e.cost;
	}
}

public class Wonder {
	static int[] arrSet;
	
	
	public static int Find(int v) {
		if(v==arrSet[v]) return v;
		else return arrSet[v] = Find(arrSet[v]);
	}
	
	public static void Union(int a, int b) {
		int fa = Find(a);
		int fb = Find(b);
		if(fa!=fb) arrSet[fa] =fb;
	}
	
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();

		ArrayList<Edge> arr = new ArrayList<>();
		arrSet = new int[n];
		for(int i=1; i<=n; i++) arrSet[i] = i; 
		for(int i=0; i<m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			arr.add(new Edge(a,b,c));	
		}
		
		int answer = 0;
		Collections.sort(arr);
		for(Edge ob : arr) {
			int fa = Find(ob.v1);
			int fb = Find(ob.v2);
			if(fa!=fb) {
				answer += ob.cost;
				Union(ob.v1, ob.v2);
			}
		}
		
		System.out.println(answer);
		
	}

}

 

💡 체크할 부분

 arrSet = new int[n]; 아닌 arrSet = new int[n+1]; 이 정답 코드인 이유를 분석해봅시다.

 

 

배열의 시작은 0인데, 위의 경우에는 arrSet[0] 이 아닌 arrSet[1]부터 저장을 시도하고 있습니다.

이러한 경우에는 n+1로 배열을 생성해주어야 정상적으로 저장이 가능합니다. 

 

 

여기서 한 가지 의문점이 들었는데요,

 

case 1.

arrSet = new int[n+1];

for(int i=1; i<=n; i++) arrSet[i]=i;

 

또는

 

case 2.

arrSet = new int[n];

for(int i=0; i<n; i++) arrSet[i]=i+1;

 

둘 다 가능하다고 이해를 했는데 case 2번 방법으로 했을 때 에러가 발생했습니다. 

에러 내용 : Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 9 out of bounds for length 9

 

 

 

해결

arrSet= new int[n];

for(int i=0; i<n; i++) arrSet[i]=i +1;

 

고민했던 이 부분에서 에러가 나는 게 아니라 이렇게 배열을 생성해 줄 시 unf[8] = 9 가 됩니다.

하지만 배열 원소의 9번째에 접근을 할 때 unf[8] 이 아닌 9를 그대로 넣어서 오류가 발생한 것이었습니다.

 

// 만약 Find(9)로 들어가는 경우
    public static int Find(int v) {
	if(v==arrSet[v]) return v; // 여기에서 arrSet[9] 조회를 시도 -> ArrayIndexOutOfBound 에러 발생 
	else return arrSet[v] = Find(arrSet[v]);
	}

arrSet[9]가 없죠... ㅎㅎㅎㅎㅎㅎ

 

위의 내용을 종합해서 코드를 다시 구현해보니 통과하였습니다!

 

 

성공 코드

package ch09;

import java.util.*;

class Edge implements Comparable<Edge> { // cost기준 오름차순 정렬 할 것 이므로 implements Comparable
	public int v1;
	public int v2;
	public int cost;
	
	// 매개변수 있는 생성자
	Edge(int v1, int v2, int cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}
	
	// 정렬시키기 위한 compareTo메서드 사용
	@Override
	public int compareTo(Edge e) {
		return this.cost - e.cost;
	}
}

public class Wonder {
	static int[] arrSet;
	
	// Find & Union 알고리즘 구현 위치!
	public static int Find(int v) {
		if(v==arrSet[v]) return v;
		else return arrSet[v] = Find(arrSet[v]);
	}
	
	public static void Union(int a, int b) {
		int fa = Find(a);
		int fb = Find(b);
		if(fa!=fb) arrSet[fa] =fb;
	}
	
	public static void main(String[] args) {
		// 입력 
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		// 간선 정보 입력 : 세 정보를 하나로 담을 객체 생성, 선 클래스 Edge생성
		// 객체정보 담을 arr 생성
		ArrayList<Edge> arr = new ArrayList<>();
		arrSet = new int[n+1]; 
		for(int i=1; i<=n; i++) arrSet[i] = i; // 1 ~ 9 arr[9]=9
		for(int i=0; i<m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			arr.add(new Edge(a,b,c));	
		}
		// 출력
		int answer = 0;
		Collections.sort(arr);
		for(Edge ob : arr) {
			int fa = Find(ob.v1);
			int fb = Find(ob.v2);
			if(fa!=fb) {
				answer += ob.cost;
				Union(ob.v1, ob.v2);
			}
		}
		
		// return answer 못 할 경우 -> System.out.println(answer);
		System.out.println(answer);
		
	}

}