[프로그래머스] 섬 연결하기 -JAVA

섬 연결하기

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

 

풀이

MST를 찾는 문제입니다.

 

기존에 크루스칼 알고리즘을 이용해서 MST를 찾는 문제를 한 번이라도 풀어봤더면 쉽게 풀 수 있는 기본 문제였습니다.

 

이러한 MST를 찾는 문제는 간선의 가중치가 나옵니다.

크루스칼 알고리즘을 이용하려면

1. 간선의 가중치를 오름차순으로 정렬한다.
2. 정렬된 간선 중 사이클을 이루지 않는 간선을 선택한다
3. 해당 간선을 MST의 집합에 추가해주면 됩니다.

 

 

먼저 간선의 가중치를 오름차순으로 정렬하는 과정입니다.

Comparable을 통해 쉽게 해줄수 있습니다.

class Node implements Comparable<Node>{
    int s,e,w;
    Node(int s, int e, int w){
        this.s=s;
        this.e=e;
        this.w=w;
    }
    @Override
    public int compareTo(Node o) {
        return this.w-o.w;
    }
}

 

 

그 다음 사이클을 찾으려면 부모 노드를 찾아야 합니다.

무슨 말이냐 하면 1->2->3 이렇게 연결된 노드 관계가 있다고 합시다.

 

1번은 2번에 연결,

2번은 3번에 연결 돼 있죠 이 연결관계를 표현하면 아래와 같습니다.

 

1번노드 (부모노드 2)

2번노드 (부모노드 3)

3번노드 (부모노드 3)

 

3번노드의 부모노드가 3인 이유는 맨 처음 부모노드는 자기 자신이고 크루스칼 알고리즘을 진행하면서 부모가 바뀝니다.

 

이 문제에는 섬(노드)가 최대 100개까지 있을수 있다하니 먼저 연결관계를 자기 자신으로 해줍시다.

x
​
parent = new int[101];
​
for(int i=1; i<=100; i++) {
    parent[i] = i;
}

 

그 다음 재귀함수를 통해 부모를 찾는 find 함수를 구현해줍니다.

이해를 해도 좋지만 코드 자체가 간단해 외우는것도 나쁘지 않아보입니다.

 

x ==parent[x] 부분은 부모를 찾은 것이고

아래 부분은 계속 부모를 타고 가는것입니다.

 

위의 예시로 들면 1->2->3 의 경우

1의 부모는 2번 입니다. 하지만 최종적으로 연결관계를 보면 2번의 부모는 3번이니 1번의 부모도 최종적으로 3번이 돼야 합니다.

parent[1] 은 2이니

1 == parent[2]는 성립되지 않고

 

parent[1] = find(2)가 되는 셈 입니다.

재귀를 다 끝내면

parent[1]에는 3이 들어가게 됩니다.

xxxxxxxxxx
public static int find(int x) {
    if(x==parent[x]) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

 

 

여태까지 부모를 구하는 과정이였고 사이클을 체크하는 방법에 대해서 알려드리겠습니다.

사이클을 체크하는 방법은 간단합니다. 2개의 노드의 최상위 부모가 똑같지 않으면 됩니다.

간단하죠?

public static boolean check(int x, int y) {
    int a = find(x);
    int b = find(y);
    if(a==b) {
    return false;
    }
    return true;
}

 

 

그 다음 합치는 과정입니다.

사이클을 이루지 않는다면 2개의 간선을 MST집합에 넣어주는 과정이라고 할 수 있습니다.

 

보통 숫자가 적은쪽이 최상위 부모로 두고 문제해결을 합니다

그래서 if문이 존재하는 것입니다.

xxxxxxxxxx
public static void union(int x, int y) {
    int a = find(x);
    int b = find(y);
​
    if(a>b) {
        int tmp = a;
        a= b;
        b = tmp;
    }
​
    parent[b] = a;
}

 

 

여기까지가 크루스칼알고리즘 , MST에 대한 개념 설명이였고 전체 풀이는 아래와 같습니다.

 

전체코드

import java.util.*;
class Solution {
    static int parent[];
    public static int solution(int n, int[][] costs) {
        int answer = 0;
        ArrayList<Node>list = new ArrayList<>();
        parent = new int[101];
        
        for(int i=1; i<=100; i++) {
            parent[i] = i;
        }
        
        for(int i=0; i<costs.length; i++) {
            list.add(new Node(costs[i][0],costs[i][1],costs[i][2]));
        }
        
        Collections.sort(list);
        
        
        for(Node a : list) {
            if(check(a.s,a.e)) {
                answer+=a.w;
                union(a.s,a.e);
            }
        }
        
        
        return answer;
    }
    public static boolean check(int x, int y) {
        int a = find(x);
        int b = find(y);
        if(a==b) {
            return false;
        }
        return true;
    }
    public static void union(int x, int y) {
        int a = find(x);
        int b = find(y);
        
        if(a>b) {
            int tmp = a;
            a= b;
            b = tmp;
        }
        
        parent[b] = a;
    }
    public static int find(int x) {
        if(x==parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
}
class Node implements Comparable<Node>{
    int s,e,w;
    Node(int s, int e, int w){
        this.s=s;
        this.e=e;
        this.w=w;
    }
    @Override
    public int compareTo(Node o) {
        return this.w-o.w;
    }
}