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

💡 문제
섬연결하기 (https://school.programmers.co.kr/learn/courses/30/lessons/42861)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• 그래프 이론(Graph Theory):
  • 그래프는 정점(Vertex)과 간선(Edge)의 집합으로 이루어진 자료 구조입니다. 각 간선은 두 개의 정점을 연결하며, 방향이 있는 경우와 없는 경우로 나뉩니다.
  • 그래프는 방향성과 가중치가 있는 경우와 없는 경우로 구분됩니다. 이 문제에서는 방향성은 고려하지 않으며, 다리의 비용을 가중치로 취급합니다.
• 최소 비용 신장 트리(Minimum Spanning Tree, MST):
  • 그래프의 모든 정점을 연결하는 트리 중에서, 간선의 가중치의 합이 최소인 트리를 의미합니다.
  • 이 때, 신장 트리는 사이클이 없어야 하며, 모든 정점이 연결되어 있어야 합니다.
  • 대표적인 알고리즘으로는 Kruskal 알고리즘과 프림 알고리즘이 있습니다.
• 탐욕법(Greedy Algorithm):
  • 탐욕법은 각 단계에서 최적의 선택을 하는 그리디한 방식으로 문제를 해결하는 알고리즘입니다.
  • 각 선택이 지역적으로는 최적이지만 전체적으로는 최적해를 보장하지 않을 수 있습니다.
  • Kruskal 알고리즘은 최소 비용 신장 트리를 구하는데에 탐욕법을 사용하는 대표적인 예시입니다.
• Union-Find 자료구조:
  • Union-Find 자료구조는 서로소 집합(Disjoint Set)을 표현하고 관리하는 자료구조입니다.
  • 각 집합을 트리로 표현하며, 두 원소가 같은 집합에 속하는지 여부를 효율적으로 판별할 수 있습니다.
  • 주요 연산으로는 원소를 합치는 Union 연산과 두 원소가 같은 집합에 속하는지를 확인하는 Find 연산이 있습니다.
  • Kruskal 알고리즘에서는 간선의 연결 여부를 확인하고 사이클을 방지하기 위해 Union-Find를 사용합니다.

---

🤓 문제 풀이

🔨 문제 설명

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

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

 

이 문제는 주어진 섬과 다리 정보를 활용하여 모든 섬을 최소 비용으로 연결하는 최적의 방법을 찾는 문제입니다. 이를 위해 Kruskal 알고리즘을 사용했습니다. 이 알고리즘은 최소 비용 신장 트리를 찾는 그리디 알고리즘 중 하나로, 주어진 그래프에서 간선의 가중치를 오름차순으로 정렬한 후, 사이클을 형성하지 않으면서 간선을 추가해 나가는 방식으로 동작합니다.

---

🔨 접근 방법

• 주어진 다리 정보를 그래프로 표현합니다. 이 때, 각 섬을 정점으로, 섬 사이의 다리를 간선으로 표현합니다.
• Kruskal 알고리즘을 사용하여 최소 비용 신장 트리를 찾습니다. 이를 위해 간선의 비용을 오름차순으로 정렬한 후, 사이클을 형성하지 않으면서 간선을 선택합니다.
• 선택한 간선들의 비용을 합산하여 최종 결과를 반환합니다.

---

🔨 문제 풀이 과정

• 최소 비용의 다리부터 선택하기:
  • 주어진 다리 정보를 비용에 따라 오름차순으로 정렬합니다. 이렇게 하면 최소 비용의 다리부터 선택할 수 있습니다.
• 사이클을 형성하지 않도록 다리 선택하기:
  • 다리들로 모든 섬을 연결하면서 사이클이 형성되지 않도록 선택합니다. 사이클을 형성하는 다리를 선택하면 안 됩니다.
  • Union-Find 자료구조를 사용하여 각 섬의 부모를 관리합니다. 이를 통해 사이클이 형성되는지를 확인할 수 있습니다.
• 모든 섬을 연결할 때까지 선택된 다리들의 비용 합산하기:
  • 정렬된 간선들을 하나씩 확인하면서 사이클을 형성하지 않으면 다리를 선택하고, 최소 비용을 갱신합니다.
  • 선택한 다리들의 비용을 합산하여 최종 결과를 반환합니다.

---

🔨 Kruskal 선택

문제를 해결하는 가장 일반적인 방법은 그래프 이론과 최소 비용 신장 트리(Minimum Spanning Tree) 알고리즘을 사용하는 것입니다. 문제에서 각 섬을 정점으로, 섬 사이의 다리를 간선으로 나타낼 수 있습니다. 이 때, 모든 섬을 연결하면서 비용을 최소화하는 것이 목표입니다.

문제를 해결하기 위해 Kruskal 알고리즘을 사용할 것입니다. 이 알고리즘은 최소 비용 신장 트리(Minimum Spanning Tree)를 찾는 그리디 알고리즘 중 하나입니다. 이 알고리즘은 간선을 비용의 오름차순으로 정렬한 후, 사이클을 형성하지 않으면서 간선을 선택하여 최소 비용 신장 트리를 만듭니다.

이 알고리즘을 구현하기 위해 Union-Find 자료구조를 사용할 것입니다. 이를 통해 사이클을 확인하고, 선택한 다리들이 서로 연결되어 있는지 확인할 수 있습니다.

---

🔨 구현코드

1) Kruskal 사용한 코드

import java.util.Arrays;

class Solution {
    public int solution(int n, int[][] costs) {
        // 1. 비용을 기준으로 오름차순으로 정렬
        Arrays.sort(costs, (a, b) -> a[2] - b[2]);
        
        // Union-Find 자료구조를 초기화합니다.
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i; // 각 섬은 처음에는 자기 자신을 가리킴
        }
        
        int answer = 0; // 최소 비용을 저장할 변수
        
        // 2. 모든 다리를 확인하면서 사이클이 형성되지 않도록 선택
        for (int[] cost : costs) {
            int island1 = cost[0];
            int island2 = cost[1];
            int bridgeCost = cost[2];
            
            // 사이클이 형성되지 않는다면 다리를 선택
            if (find(parent, island1) != find(parent, island2)) {
                union(parent, island1, island2);
                answer += bridgeCost; // 비용 추가
            }
        }
        
        return answer;
    }
    
    // Union-Find의 Find 연산
    private int find(int[] parent, int island) {
        if (parent[island] != island) {
            parent[island] = find(parent, parent[island]);
        }
        return parent[island];
    }
    
    // Union-Find의 Union 연산
    private void union(int[] parent, int island1, int island2) {
        int root1 = find(parent, island1);
        int root2 = find(parent, island2);
        parent[root2] = root1;
    }
}

 

2)다른 방식

import java.util.Arrays;

class Solution {
    public int solution(int n, int[][] costs) {
        // 1. 비용을 기준으로 오름차순으로 정렬
        Arrays.sort(costs, (a, b) -> a[2] - b[2]);
        
        // Union-Find 자료구조를 초기화합니다.
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i; // 각 섬은 처음에는 자기 자신을 가리킴
        }
        
        int answer = 0; // 최소 비용을 저장할 변수
        
        // 2. 모든 다리를 확인하면서 사이클이 형성되지 않도록 선택
        for (int[] cost : costs) {
            int island1 = cost[0];
            int island2 = cost[1];
            int bridgeCost = cost[2];
            
            // 사이클이 형성되지 않는다면 다리를 선택
            if (find(parent, island1) != find(parent, island2)) {
                union(parent, island1, island2);
                answer += bridgeCost; // 비용 추가
            }
        }
        
        return answer;
    }
    
    // Union-Find의 Find 연산
    private int find(int[] parent, int island) {
        if (parent[island] != island) {
            parent[island] = find(parent, parent[island]);
        }
        return parent[island];
    }
    
    // Union-Find의 Union 연산
    private void union(int[] parent, int island1, int island2) {
        int root1 = find(parent, island1);
        int root2 = find(parent, island2);
        parent[root2] = root1;
    }
}

---

📚 풀이 보완

코드 설명

1. solution 메서드: 주어진 섬의 개수 n과 다리 정보 배열 costs를 받아서 최소 비용으로 모든 섬을 연결하는 함수입니다.
   • 먼저 costs 배열을 다리의 비용에 따라 오름차순으로 정렬합니다.
   • Union-Find 자료구조를 초기화합니다. 각 섬은 처음에는 자기 자신을 가리키도록 합니다.
   • answer 변수는 최소 비용을 저장하고, edges 변수는 선택한 간선의 수를 저장합니다.
   • 이후, 모든 다리를 확인하면서 사이클이 형성되지 않도록 선택한 다리들로 모든 섬을 연결합니다. 이를 위해 for문을 사용합니다.
   • 선택한 다리가 사이클을 형성하지 않으면 선택하고, 그 비용을 answer에 추가합니다.
   • 모든 섬을 연결한 후에는 함수를 종료합니다.
2. find 메서드: Union-Find의 Find 연산을 구현한 메서드입니다. 재귀적으로 부모를 찾아가며 최종 부모를 반환합니다.
3. union 메서드: Union-Find의 Union 연산을 구현한 메서드입니다. 두 섬을 연결할 때, 각 섬의 최상위 부모를 찾아서 연결합니다.

Kruskal 알고리즘을 구현한 것으로, Union-Find 자료구조를 사용하여 사이클을 방지하면서 최소 비용 신장 트리를 구성합니다.

---

📍 Plus+

공간 복잡도

공간 복잡도는 주로 사용되는 자료구조의 크기와 관련이 있습니다. 이 문제에서 사용하는 주요 자료구조는 Union-Find입니다. Union-Find 자료구조에서는 각 정점(섬)을 나타내는 배열과 부모를 나타내는 배열이 필요합니다. 또한, 최종적으로 반환되는 최소 비용을 저장하는 변수가 있습니다.

따라서 공간 복잡도는 다음과 같이 계산됩니다:

• 섬의 개수를 나타내는 배열: O(n)
• Union-Find 자료구조를 위한 부모 배열: O(n)
• 최소 비용을 저장하는 변수: O(1)

따라서 전체 공간 복잡도는 O(n)입니다.

시간복잡도

시간 복잡도는 주로 사용되는 알고리즘의 수행 시간과 관련이 있습니다. 이 문제에서는 Kruskal 알고리즘을 사용하여 최소 비용 신장 트리를 구성합니다. 주요 연산인 간선을 비용에 따라 정렬하는 과정과 간선을 선택하고 Union-Find 연산을 수행하는 과정이 있습니다.

따라서 시간 복잡도는 다음과 같이 계산됩니다:

• 간선 정렬: O(E log E) (E는 간선의 수)
• 간선 선택과 Union-Find 연산: O(E α(V)) (α는 역 Ackermann 함수로 상수에 가까운 값)

따라서 전체 시간 복잡도는 O(E log E + E α(V))입니다.

요약

• 공간 복잡도: O(n)
• 시간 복잡도: O(E log E + E α(V))

---

오늘 푼 문제 개념 정리

주어진 문제는 Kruskal 알고리즘을 탐욕법(그리디) 알고리즘으로 해결해야 하며, 그 과정에서 Union-Find 자료구조를 사용해야 합니다. Kruskal 알고리즘은 탐욕법 알고리즘 중 하나로, 각 단계에서 가장 작은 비용의 간선을 선택하여 신장 트리를 만들어가는 그리디 방식입니다.

그래서 문제를 해결하는 방법은 Kruskal 알고리즘을 사용하여 최소 비용 신장 트리를 찾고, 이 과정에서 Union-Find 자료구조를 사용하여 사이클을 방지하는 것입니다. 이를 통해 모든 섬을 최소 비용으로 연결할 수 있습니다.

그러므로 위에 구현한 코드는 Kruskal 알고리즘을 사용하고 있으며, Union-Find 자료구조를 활용하고 있습니다.

또 다른 자료구조로는 최소 힙을 사용한 프림 알고리즘이 있습니다.

최소 비용 신장 트리를 찾는 문제를 해결하는 데 Union-Find 외에도 다른 자료구조를 사용할 수 있습니다. 대표적으로는 크루스칼 알고리즘에서는 Union-Find를 주로 사용하지만, 최소 힙(최소 힙을 사용한 프림 알고리즘)도 사용할 수 있습니다.

프림 알고리즘은 각 단계에서 이미 선택된 정점 집합과 선택되지 않은 정점들을 연결하는 최소 비용의 간선을 선택해가며 최소 비용 신장 트리를 구성합니다. 이 과정에서 최소 힙을 사용하여 간선을 선택하는데, 이는 선택된 간선들 중 가장 작은 비용의 간선을 빠르게 찾을 수 있도록 합니다.

따라서 프림 알고리즘을 구현할 때에는 최소 힙을 사용하여 간선의 비용을 관리하고, 이미 선택된 정점과 선택되지 않은 정점들을 구분하여 최소 비용 신장 트리를 만들어갑니다.

그러나 이 문제에서는 주어진 조건이 Kruskal 알고리즘과 Union-Find 자료구조를 사용하도록 요구하고 있으므로, Kruskal과 Union-Find를 중심으로 구현하는 것이 적절합니다.

 

 

---

이모저모..

 

람다식은 Arrays.sort 메서드에서 사용

Arrays.sort(costs, (a, b) -> Integer.compare(a[2], b[2]));