[프로그래머스/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를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

[코드]

import java.util.Arrays; import java.util.Comparator; class Solution {     int[] parent; //부모 노드 저장     public int solution(int n, int[][] costs) {         int answer = 0;         parent = new int[n];         for (int i = 0 ; i < n ; i++) parent[i] = i;         Arrays.sort(costs, new Comparator<int[]>() { //가중치가 낮은 순으로 정렬             @Override             public int compare(int[] o1, int[] o2) {                 return o1[2] - o2[2];             }         });         for (int i = 0; i < costs.length; i++) {             int prev = costs[i][0];             int front = costs[i][1];             int cost = costs[i][2];             int prevParent = findParent(prev); //부모 노드 검색             int frontParent = findParent(front);             if (prevParent==frontParent) continue; //부모 노드가 같다면, 넘긴다.             answer += cost;             parent[frontParent] = prevParent;         }         return answer;     }     private int findParent(int node){ //부모 노드 검색 메소드         if (parent[node]==node) return node;         return parent[node] = findParent(parent[node]);     } }

해당 문제에서 요구하는 정답은 Minimum Spanning Tree(MST) 이다.

한국어로는 최소 신장 트리라고 하는데, 이번 문제에서 조건으로 주어진 최소의 가중치를 가진 간선으로 노드를 연결하는 트리이다.

 

최소 신장 트리는 사이클이라는 개념이 있는데, 이번 문제의 설명 중에 A와 B가 연결되어있고 A와 C가 연결되어있다면 B와 C는 연결되어있다는 표현과 상이하다. 사이클이 있다는 의미는 이번 문제에서 B와 C가 간선으로 연결되어있다는 뜻과 같다. 즉 연결되지 않아도 되는 간선이 연결되어있다는 뜻이다. 사이클이 없다면 B와 C가 직접 연결되어있지 않지만 A를 통해 왔다갔다 할 수 있는 상태를 의미한다. 이번 문제에서 쓰이지는 않지만 사이클이 없는 최소 신장 트리는 (노드의 개수 -1) 개의 간선을 가지고 있다.

사이클이 있는 트리

위의 그림은 입출력 예의 그림을 수정한 것인데, 2와 3의 간선이 연결된 것으로 사이클이 있는 트리이다.

4개의 노드를 가진 최소 신장 트리는 (4-1)개의 간선을 가지기 때문이라 설명할 수 있겠지만, 달리 설명하면 2와 3이 연결되어 있지 않아도 0과 1을 통해 이동이 가능하기 때문에 불필요한 간선이 있기 때문에 사이클이 있다고 설명할 수도 있다.

 

이번 문제를 풀기 위해서 Union-Find와 Kruskal 알고리즘을 이해할 필요가 있다.

Union-Find는 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위한 자료구조인데 두 가지 연산으로 나눌 수 있다.

Union 연산은 서로 다른 집합을 하나의 집합으로 병합하는 연산을 의미하고

Find 연산은 하나의 요소가 어떤 집합에 속해있는지 판단하는 연산이다.

Kruskal 알고리즘은 최소 신장 트리를 만들기 위한 알고리즘이다.

 

이 그림은 Union-Find 개념을 이용한 그림이다.

특정 요소를 부모 노드로 설정하고 나머지 요소를 자식 노드로 설정한다.

노드 1, 2, 3의 부모 노드가 0이라면 노드 1, 2, 3은 특정 집합에 속해있다고 할 수 있다.

 

노드의 부모노드를 설정하는 과정을 알아보자.

노드	0	1	2	3
부모 노드	0	1	2	3

초기에는 각 노드는 자신의 노드 정보만을 가지고 있다.

여기서 주어진 배열 costs = [[0,1,1], [0,2,2], [1,2,5], [1,3,1], [2,3,8]] 를 사용해보자.

처음부터 시작해서 [0,1,1] 을 적용한다면

노드	0	1	2	3
부모 노드	0 또는 1	0 또는 1	2	3

노드 0과 1은 연결해있기 때문에 노드 0과 1의 부모 노드를 0으로 설정할 수 있다.

여기서 부모 노드는 정해져있는 것이 아니기 때문에 1로 설정해도 된다.

[0,2,2]를 적용하고 부모 노드를 1로 설정한다면

노드	0	1	2	3
부모 노드	1	1	1	3

여기서 노드 0과 2가 연결되어있기 때문에 노드 2의 부모 노드는 노드 0의 부모 노드와 같다고 설정할 수 있다.

마지막으로 [1,3,1]을 적용한다면

노드	0	1	2	3
부모 노드	1	1	1	1

노드 1과 3도 서로 연결되어있기 때문에 부모 노드가 동일하다고 설정할 수 있다.

 

이제 중요한 점, 가중치가 남아있다.

만들고자 하는 최소 신장 트리는 가장 작은 가중치로 만들어야 한다.

이를 위해서 문제에서 주어진 costs 배열을 가중치를 기준으로 오름차순을 해야한다.

Arrays.sort(costs, new Comparator<int[]>() { //가중치가 낮은 순으로 정렬</int[]>             @Override             public int compare(int[] o1, int[] o2) {                 return o1[2] - o2[2];             }  });

이제 가중치가 낮은순으로 노드간의 부모 노드를 통일 시키는 과정을 하면 된다.

그리고 가중치가 낮은 순서부터 통일을 하기 때문에 가중치를 바로 더해준다.

이때 부모 노드가 이미 같게 되어있다면 더 낮은 가중치로 통일이 이미 되어있기 때문에 넘긴다.