프로그래머스 - 섬 연결하기 (sol.java)
◎문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42861
코딩테스트 연습 - 섬 연결하기
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
programmers.co.kr
◎문제 파악
모든 섬을 연결하는 최소비용 구하기
- 최소비용을 구하는 문제이므로, 그리디 알고리즘을 이용하여 섬을 잇는 비용(간선 값)이 가장 작은 섬들부터 이어가야한다. --> 간선 값을 기준으로 정렬(heap 자료구조 사용, array로 넣어서 정렬하는것보다 빠르다)
- 각 섬들이 어떤 섬과 이어졌는지 파악하기 위해서 배열(connect)을 만들어 이어진 섬 중에 가장 작은 번호의 섬을 집어 넣는다. 모든 배열의 값이 0이 되면(섬의 번호 중 가장 작은 번호가 0이므로 ), 모든 섬이 연결된 것으로 파악하고 반복을 종료한다.
예시를 보면서 문제를 다시 파악하자
ex. n = 4 , costs = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
1. 힙 생성 및 costs 입력
간선 값을 기준으로 정렬: [0,1,1], [1,3,1], [0,2,2], [1,2,5], [2,3,8]
(설명의 용이성을 위해 완전 정렬해 두었지만, 프로그램 상으로는 느슨히 정렬되어있다.)
2. 배열 connect 생성 처음엔 연결된 간선이 없으므로, 연결되어 있는 섬 중 가장 작은 값은 자기 자신이다
| 섬 번호 | 0 | 1 | 2 | 3 |
| 연결된 섬 중 가장 작은 값 | 0 | 1 | 2 | 3 |
3. 힙에서 최소값 반환 :[0,1,1]
0번 섬과 1번 섬 연결
비용: 1
| 섬 번호 | 0 | 1 | 2 | 3 |
| 연결된 섬 중 가장 작은 값 | 0 | 0 | 2 | 3 |
->모든 섬이 연결되지 않았으므로 (모든 값이 0이 아니므로) 반복
4. 힙에서 최소값 반환: [1,3,1]
1번 섬과 3번 섬 연결
비용: 1+1 = 2
| 섬 번호 | 0 | 1 | 2 | 3 |
| 연결된 섬 중 가장 작은 값 | 0 | 0 | 2 | 0 |
->모든 섬이 연결되지 않았으므로 (모든 값이 0이 아니므로) 반복
5. 힙에서 최소값 반환: [0,2,2]
0번 섬과 2번 섬 연결
비용: 2+2 = 4
| 섬 번호 | 0 | 1 | 2 | 3 |
| 연결된 섬 중 가장 작은 값 | 0 | 0 | 0 | 0 |
-> 모든 섬이 연결되었으므로 반복 종료
최종 비용: 4
◎코드 구현
package Programmers.ConnectingIslands;
import java.util.Comparator;
import java.util.PriorityQueue;
class MySolution {
public int solution(int n, int[][] costs) {
int answer = 0;
//연결되어 있는 섬 중 가장 작은 값을 나타내는 connect 배열
//처음엔 연결된 다리가 없으므로, 연결되어 있는 섬 중 가장 작은 값은 자기 자신이다
int[] connect = new int[n];
for(int i = 0; i<n; i++) {
connect[i] = i;
}
//비용 값을 기준으로 최소 힙 구현
PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
// TODO Auto-generated method stub
return a[2] - b[2];
}
});
for(int[] value : costs) {
heap.add(value);
}
int allconnect = -1;
//모든 섬이 연결될때까지 반복
while(allconnect!=0) {
//비용이 가장 작은 순서대로 반환
int[] tmp = heap.poll();
//서로 연결되어있는 섬이 아니면 서로 연결
if(connect[tmp[0]]!= connect[tmp[1]] ) {
if(connect[tmp[0]]>connect[tmp[1]]) {
update(connect, connect[tmp[1]],connect[tmp[0]]);
}else {
update(connect, connect[tmp[0]],connect[tmp[1]]);
}
answer = answer + tmp[2];
//connect 배열의 모든 원소가 0(connect[0]의 값,
//노드중에 가장 작은 값)이면, 모든 노드가 연결된 것이다
allconnect = connect[0];
for(int con : connect) {
if(con != allconnect) {
allconnect = -1;
break;
}
}
}
}
return answer;
}
//모든 이어진 섬들의 값을 가장 최소 노드 값으로 최신화
public void update(int[] connect, int newone, int oldone) {
for(int i = 0; i< connect.length; i++) {
if(connect[i]==oldone) {
connect[i] = newone;
}
}
}
public static void main(String[] args) {
int[][] costs = {{0,2,1},{1,2,2},{2,3,2},{0,4,2},{2,4,2}} ;
MySolution sol = new MySolution();
System.out.println(sol.solution(5,costs));
}
}※update 메서드의 존재 이유:
| 섬 번호 | 0 | 1 | 2 | 3 |
| 연결된 섬 중 가장 작은 값 | 0 | 0 | 2 | 2 |
인 경우 (0번 섬과 1번 섬만 이어져있고, 2번 섬과 3번 섬만 이어져있는 경우)
힙에서 반환된 값이 [1,2,1]일때, update 메서드가 없다면,
| 섬 번호 | 0 | 1 | 2 | 3 |
| 연결된 섬 중 가장 작은 값 | 0 | 0 | 0 | 2 |
과 같이 방금 연결된 섬만 가장 작은 값으로 바뀐다. 그러므로 update 메서드를 사용하여
가장 작은 값이 2였던 섬들(2번 섬과 연결되어있는 섬들)을 모두 0으로 바꾸어주어야한다.
◎ 크루스칼 알고리즘을 통한 풀이
크루스칼 알고리즘이란?
https://kkwong-guin.tistory.com/61
Java - 크루스칼 알고리즘(Kruskal)
◎최소 스패닝 트리(minimum spanning tree) 스패닝 트리(spannig tree)란 신장 트리라고도 하며, 그래프 내의 모든 정점을 사이클 없이 포함하는 트리를 말한다. 하나의 그래프는 여러 개의 스패닝 트리를
kkwong-guin.tistory.com
코드:
package Programmers.ConnectingIslands;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Kruskal_solution {
//부모 노드를 가져옴
public int getParents(int set[], int x) {
if(set[x] == x) return x;
//재귀 함수를 통해 그래프 중에 가장 작은 부모 노드의 값을 가져온다
return set[x] = getParents(set, set[x]);
}
//부모 노드 병합
void unionParent(int set[], int a, int b) {
a = getParents(set, a);
b = getParents(set,b);
if(a<b) set[b] = a;
else set[a]=b;
}
//같은 부모를 가지는지 확인
boolean find(int set[], int a, int b) {
a = getParents(set,a);
b = getParents(set,b);
if(a==b) return false;
else return true;
}
public int solution(int n, int[][] costs) {
int answer = 0;
//연결되어 있는 섬 중 가장 작은 값을 나타내는 connect 배열
int[] connect = new int[n];
for(int i = 0; i<n; i++) {
connect[i] = i;
}
PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
// TODO Auto-generated method stub
return a[2] - b[2];
}
});
for(int[] value : costs) {
heap.add(value);
}
//힙이 빌때까지(모든 간선 값을 볼때까지) 반복
while(!heap.isEmpty()) {
int[] tmp = heap.poll();
if(find(connect, connect[tmp[0]], connect[tmp[1]])) {
unionParent(connect, connect[tmp[0]], connect[tmp[1]]);
answer = answer + tmp[2];
}
}
return answer;
}
public static void main(String[] args) {
int[][] costs = {{0,2,1},{1,2,2},{2,3,2},{0,4,2},{2,4,2}} ;
MySolution sol = new MySolution();
System.out.println(sol.solution(5,costs));
}
}
◎ 프림 알고리즘을 기반한 풀이
프림 알고리즘이란?
https://kkwong-guin.tistory.com/62
Java - 프림 알고리즘(Prim)
◎프림 알고리즘(Kruskal) 프림 알고리즘은 노드를 중점으로 그리디하게 최소 스패닝 트리(MST)를 찾는 알고리즘이다. 영역을 단계적으로 넓혀간다고 생각하면 이해하기 편하다. ※MST의 정의와 MST
kkwong-guin.tistory.com
코드:
package Programmers.ConnectingIslands;
import java.util.ArrayList;
import java.util.Iterator;
class Solution {
public int solution(int n, int[][] costs) {
//섬과 간선을 나타내는 2차원 배열 island 생성
int[][] island = new int[n][n];
//한쪽 섬을 시점, 다른 쪽 섬을 종점으로 생각하고 섬을 연결하는 비용(간선) 저장
for (int[] cost : costs) {
if (cost.length > 0) {
island[cost[0]][cost[1]] = cost[2];
island[cost[1]][cost[0]] = cost[2];
}
}
//연결되어있는 섬을 저장하는 배열 connected
ArrayList<Integer> connected = new ArrayList<>();
Iterator<Integer> it;
//0번째 섬부터 연결을 시작한다
connected.add(0);
/*
* 섬을 모두 연결하는 최소 비용을 구하기 위해서는
* 비용이 낮은 간선을 선택해야하고, 간선의 개수가 적어야한다.
* 섬을 모두 이을 수 있는 최소 간선의 개수는 섬의 수 -1이며,
* 어느 경우에도 선택된 간선의 수가 최소 간선 수를 넘으면
* 최소 비용이 될 수 없다.
*/
int sum = 0;
//연결된 섬이 n이 되면 종료 == 간선의 수가 섬의 개수 -1이면 종료
while (connected.size() < n) {
long min = -1;
int minI = -1, minJ = -1;
it = connected.iterator();
while (it.hasNext()) {
/*
* 시점이 될 수 있는 섬들은 종점이 될 수 없다.
* 0번 섬부터 시작하여, 이어진 섬들(시점이 될 수 있는 섬)에서
* 이어지지 않은 섬(종점이 될 수 있는 섬)들로 간선을 이을 것이므로
* 이어진 섬을 다시 잇는 것은 불필요하게 간선을 택한 것이다.
*/
int start = it.next();
for (int end = 0; end < n; end++) {
// 시점이 되었던 섬들은 종점이 될 수 없다.
if (!connected.contains(end)) {
if (island[start][end] > 0) {
//시점인 섬과 연결될 수 있는 모든 종점의 섬 중에 간선의 값이 가장 작은 섬을 선택한다.
if (island[start][end] < min || min == -1) {
min = island[start][end];
minI = start;
minJ = end;
}
}
}
}
}
sum += min;
//시점 후보로 종점이 된 섬 추가
connected.add(minJ);
island[minI][minJ] = 0;
island[minJ][minI] = 0;
}
return sum;
}
public static void main(String[] args) {
int[][] costs = {{0,2,1},{1,2,2},{2,3,2},{0,4,2},{2,4,2}} ;
MySolution sol = new MySolution();
System.out.println(sol.solution(5,costs));
}
}이 코드의 이해하기 위해 필요한 개념
1. 섬을 모두 이을 수 있는 최소 간선의 개수는 섬의 수 -1
3개의 섬이 있으면, 2개의 간선만으로 모두 이을 수 있다.
더 깊이 생각해보면, 간선이 최소일때, 비용이 최소일 수 있다. 어떤 경우에도 선택된 간선수가 최소 간선의 수(섬의 수 -1)를 넘으면 최소 비용이 될 수 없다. 즉, 불필요한 간선을 선택한 것이다.
2. 섬을 잇는 행위를 시점과 종점으로 나눠서 생각
0번 섬과 1번 섬을 이었다면, 0번이 시점, 1번이 종점으로 보아도 되고, 1번이 시점, 0번이 종점이라 보아도 된다.
3. 시점이 될 수 있는 섬은 종점이 될 수 없음(이미 이어진 섬은 다시 이을 필요가 없음)
0번 섬부터 시작하여, 이어진 섬들(시점이 될 수 있는 섬)에서 이어지지 않은 섬(종점이 될 수 있는 섬)들로 간선을 이을 것이므로 이어진 섬을 다시 잇는 것은 불필요하게 간선을 택한 것이다.
예시를 보면서 코드를 파악하자
ex. n = 4 , costs = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
1. 섬을 잇는 행위를 시점과 종점으로 나눠서 생각하는 것에 의해,
<배열 island>
| start/end | 0 (x) | 1 (o) | 2 (o) | 3 (o) |
| 0 (o) | 1(slected) | 2 | ||
| 1 (x) | 1 | 5 | 1 | |
| 2 (x) | 2 | 5 | 8 | |
| 3 (x) | 1 | 8 |
<connected>
0
connected에 처음에 0을 넣었으므로, start가 될 수 있는 섬은 0, end가 될 수 있는 섬은 0을 제외한 1~3이다.
그중에서 가장 작은 값은 시점이 0이고, 종점이 1인 연결이다.
종점을 connected에 추가해준다.
2. connected.size()가 섬의 개수보다 작으므로 반복
<배열 island>
| start/end | 0 (x) | 1 (x) | 2 (o) | 3 (o) |
| 0 (o) | 1 | 2 | ||
| 1 (o) | 1 | 5 | 1(slected) | |
| 2 (x) | 2 | 5 | 8 | |
| 3 (x) | 1 | 8 |
<connected>
0, 1
start가 될 수 있는 섬은 0,1, end가 될 수 있는 섬은 0,1을 제외한 2,3이다.
그중에서 가장 작은 값은 시점이 1이고, 종점이 3인 연결이다.
종점을 connected에 추가해준다.
3. connected.size()가 섬의 개수보다 작으므로 반복
<배열 island>
| start/end | 0 (x) | 1 (x) | 2 (x) | 3 (o) |
| 0 (o) | 1 | 2 | ||
| 1 (o) | 1 | 5 | 1 | |
| 2 (0) | 2 | 5 | 8 | |
| 3 (x) | 1 | 8 |
<connected>
0, 1, 3
start가 될 수 있는 섬은 0,1,3, end가 될 수 있는 섬은 0,1,3을 제외한 2이다.
그중에서 가장 작은 값은 시점이 0이고, 종점이 2인 연결이다.
종점을 connected에 추가해준다.
4. connected.size()가 섬의 개수와 같으므로 반복 중지
git code: