[JAVA] Programmers <Greedy LV3> 섬 연결하기

오늘 아침도 기분 좋게...? 문제 풀이로 시작하려 했는데.... 이게 머선 129...

LV2 문제가 존재하지 않는다....(뭐야...내 LV2 돌려줘요...) 

아직 Greedy 활용 문제들이 많이 어려워서 LV2 문제 딱 하나만 더 풀었으면 좋겠는데...

아쉽지만, 그래도 할건 해야지... 바로 문제로 들어가자

---

즉, 예제의 입력을 그림으로 나타내면 다음과 같다.

굉장히 익숙한 그림이다. 사실, 어제 이 문제를 풀다가 도저히 안 되겠어서 Union-Finf, Kruskal 알고리즘을 공부하고 왔다... 하하 LV3 문제들은 보통 이런 선행학습이 꼭 필요한 경우들이 많아서...ㅠ

아무튼 오래 생각하지 않아도, 이 문제는 그냥 어제 코드를 짰던 Kruskal알고리즘을 활용하면 어려울 거 하나도 없이 풀린다.

풀이 순서를 다시 한번 확인해보면,

 1. 비용을 기준으로 배열들을 오름차순 정렬한다. 

 2. 두 노드가 연결되어 있는 지 Find로 확인한다.

 3. 연결이 되어 있지 않고, 다음 연결이 Cycle을 만들지 않는 경우

 4. Union으로 두 노드의 부모 노드를 동일하게 만든다.

 

바로 한번 코드를 작성해보자

---

package com.choonham;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {
	public int solution(int n, int[][] costs) {
		
		int answer = 0;
		List<Edge> edgeList = new ArrayList<>();
		int[] parent = new int[costs.length];
		
		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}
		
		for(int i = 0; i < costs.length; i++) {
			edgeList.add(new Edge(costs[i][0], costs[i][1], costs[i][2]));
		}
		
		Collections.sort(edgeList, new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return (o1.cost < o2.cost ? -1 : ((o1.cost == o2.cost) ? 0 : 1));
			}
		});
		
		int sum = 0;
		
		for(int i = 0; i < edgeList.size(); i++) {
			Edge edge = edgeList.get(i);
			if(!this.findParent(parent, edge.v1, edge.v2)) {
				sum += edge.cost;
				unionParent(parent, edge.v1, edge.v2);
			}
		}
		
		answer = sum;
		return answer;
	}

	// ====================Union-Find=================//
	public int getParent(int parent[], int x) {
		if (parent[x] == x)
			return x; // 부모노드가 자기 자신일 경우, 재귀 stop
		return parent[x] = getParent(parent, parent[x]); // 아닐 경우 한번 더 진행
	}

	// 부모 노드의 크기를 비교 후 작은 값을 큰 값의 부모로
	public void unionParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a < b)
			parent[b] = a;
		else
			parent[a] = b;
	}

	// 두 수가 서로 연결되어 있는 지 판단
	public boolean findParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a == b)
			return true;
		else
			return false;
	}
}

class Edge {
	public int v1;
	public int v2;
	public int cost;

	public Edge() {
	}

	public Edge(int v1, int v2, int cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}
}

 

무적권 되겠지...? 

확인해보면

---

아니 왜요...? 

다행인 건 딱 1개의 테케가 다른 원인도 아니고 "런타임 에러" 라는 것이다. 런타임 에러는 경험상 사이즈가 작은 테스트 케이스를 몇개 넣어보면 바로 이클립스가 에러를 뱉어서 찾아낼 수 있다는 건데... 

차근차근 반례를 찾아보자

가장 작은 테스트 케이스, 섬이 2개이고 간선은 1개 뿐이 없을 때를 넣어보면,

 

...? 이왜진;; 운이 좋은건지, 한번에 찾았다.

이 경우, 부모 노드를 costs의 길이를 기반으로 생성했기 때문에 노드가 2개인데도 길이 1을 가진 부모 노드가 생성이 된다.

즉, 없는 부모를 찾고 있으니 에러가 나오는 것.... 

드디어 갈 곳을 잃은 변수 n을 활용할 수 있다! (아니 애초에 그랬어야 했다. parent는 간선이 아닌 노드 기준이니....)

parent 배열의 선언부에서 int[] parent = new int[costs.length]  -->  int[] parent = new int[n] 로 바꿔주면 해결 가능한 에러이다.

바꿔주면 전체 코드는 이렇게 된다.

---

package com.choonham;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {
	public int solution(int n, int[][] costs) {

		int answer = 0;
		List<Edge> edgeList = new ArrayList<>();
		int[] parent = new int[n];

		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}

		for (int i = 0; i < costs.length; i++) {
			edgeList.add(new Edge(costs[i][0], costs[i][1], costs[i][2]));
		}

		Collections.sort(edgeList, new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return (o1.cost < o2.cost ? -1 : ((o1.cost == o2.cost) ? 0 : 1));
			}
		});

		int sum = 0;

		for (int i = 0; i < edgeList.size(); i++) {
			Edge edge = edgeList.get(i);
			if (!this.findParent(parent, edge.v1, edge.v2)) {
				sum += edge.cost;
				unionParent(parent, edge.v1, edge.v2);
			}
		}

		answer = sum;
		return answer;
	}

	// ====================Union-Find=================//
	public int getParent(int parent[], int x) {
		if (parent[x] == x)
			return x; // 부모노드가 자기 자신일 경우, 재귀 stop
		return parent[x] = getParent(parent, parent[x]); // 아닐 경우 한번 더 진행
	}

	// 부모 노드의 크기를 비교 후 작은 값을 큰 값의 부모로
	public void unionParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a < b)
			parent[b] = a;
		else
			parent[a] = b;
	}

	// 두 수가 서로 연결되어 있는 지 판단
	public boolean findParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a == b)
			return true;
		else
			return false;
	}
}

class Edge {
	public int v1;
	public int v2;
	public int cost;

	public Edge() {
	}

	public Edge(int v1, int v2, int cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}
}

---

언제나 기분 좋은 화면~ 

 

 

 

 

끝!!