[Lv.3] 프로그래머스 - 섬 연결하기 : Java

프로그래머스

 

 

dfs하면 되려나? 했는데... 손도 못 대다가 검색해보니 크루스칼 알고리즘...? 으로 풀이하라고 한다.

위 예시 그래프가 MST라고 하는데, 개념들부터 정리해야 할 것 같다.

 

신장트리
무방향 그래프 G(V, E)에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프
그래프에서 신장 트리는 여러 형태로 존재할 수 있으며, 특징으로는 N개의 정점을 갖는 그래프에서 신장트리의 간선은 n - 1개이며 사이크를 갖지 않는다는 특징이 있다.

MST
최소 비용을 가지는 신장 트리
무방향 그래프들 사이에서 간선에 가중치가 주어진 경우, 여러 개의 신장 트리 중 간선들의 가중치 합이 최소인 트리

크루스칼 알고리즘
MST를 구하는 알고리즘
그리디하게 모든 정점을 최소 비용으로 연결

크루스칼 알고리즘의 핵심
: 모든 간선을 가중치 기준으로 오름차순 정렬 → 간선들을 순서대로 모든 정점이 연결될 때까지 연결

Union-find 알고리즘을 이용하여 구현 가능

Union-find 알고리즘 (합집합 찾기 알고리즘)
대표적인 그래프 알고리즘

여러 노드가 존재할 때, 두 개의 노드를 선택하여 현재 두 노드가 서로 같은 그래프에 속하는지 판별
- Find : x가 어떤 집합에 포함되어 있는지 찾는 연산
- Union : x와 y가 포함되어 있는 집합을 합치는 연산

 

참고한 블로그⬇️

Java - [프로그래머스]42861-섬 연결하기-Kruskal/Prim

 

위에 나온 개념들을 종합해서 정리하면 다음과 같다.

• 그래프의 간선들을 가중치를 기준으로 오름차순 정렬
• 정렬된 간선 리스트를 순서대로 선택하여 간선의 정점들을 연결
  • Union-Find의 Union 사용
• 만약 간선의 두 정점 a, b가 연결되어 있다면 스킵

 

문제풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] parent = new int[n];

        for (int i = 0; i < parent.length; 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++) {
            if (findParent(parent, costs[i][0]) != findParent(parent, costs[i][1])) {
                answer += costs[i][2];
                union(parent, costs[i][0], costs[i][1]);
            }
        }

        return answer;
    }

    public int findParent(int[] parent, int node) {
        if (parent[node] == node) {
            return node;
        }

        return findParent(parent, parent[node]);
    }

    public void union(int[] parent, int node1, int node2) {
        int p1 = findParent(parent, node1);
        int p2 = findParent(parent, node2);

        if (p1 < p2) {
            parent[p2] = p1;
        } else {
            parent[p1] = p2;
        }
    }
}

 

먼저 살펴봐야 할 것은 Union-find와 관련된 두 함수이다.

    public int findParent(int[] parent, int node) {
        if (parent[node] == node) {
            return node;
        }

        return findParent(parent, parent[node]);
    }

 

findParent 함수는 parent 배열과 노드를 파라미터로 받아서 해당 노드의 부모를 찾는 함수이다.

만약 parent[node]가 node와 같다면 node를 반환하고, 아니라면 재귀적으로 함수를 돈다.

 

예를 들어 0의 부모가 0이라면 그저 0을 반환해주고 끝나면 되지만

 

 

 

 

그림과 같이 2의 부모를 찾으라고 하면 맨 위의 부모까지 찾아가야 한다.

처음 2의 부모를 찾으면 1

그 다음 1의 부모를 찾으면 0

0의 부모는 자기 자신이니 0을 반환하게 되는 것이다.

 

 

 

 

 

    public void union(int[] parent, int node1, int node2) {
        int p1 = findParent(parent, node1);
        int p2 = findParent(parent, node2);

        if (p1 < p2) {
            parent[p2] = p1;
        } else {
            parent[p1] = p2;
        }
    }

 

union 함수는 node1과 node2의 부모를 하나로 통일시키는 함수이다.

node1과 node2가 서로 연결되어 있을 때 사용한다.

 

node1의 부모 p1과 node2의 부모 p2를 각각 찾고, p1과 p2값을 비교하여 더 작은 값을 모두의 부모로 만든다.

 

    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] parent = new int[n];

 

solution 함수로 돌아와서 처음부터 봐보자.

parent는 각 노드의 부모 노드를 저장해두기 위한 배열이다.

 

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            Arrays.sort(costs, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[2] - o2[2];   // 가중치 기준 오름차순 정렬
                }
            });
        }

 

처음에는 각 노드의 부모를 자기 자신으로 하기 위해 parent[i] = i를 해준다.

그 다음 costs 배열을 가중치를 기준으로 오름차순 정렬해준다.

 

        for (int i = 0; i < costs.length; i++) {
            if (findParent(parent, costs[i][0]) != findParent(parent, costs[i][1])) {
                answer += costs[i][2];
                union(parent, costs[i][0], costs[i][1]);
            }
        }

 

정렬된 costs 배열을 돌면서 서로 부모가 다르다면 (연결되어 있지 않다면) answer에 costs[i][2]를 더해주고, 두 노드를 union 해준다.

 

 

 

크루스칼 알고리즘이나 Union-find, MST 등 몰랐던 개념들이라서 어렵게만 느껴졌다.

한 번 정리하고 다시 보니 이제 조금 감이 잡힌다.