[알고리즘 문제풀이] 프로그래머스 - 섬 연결하기

yourjin·2022년 2월 27일

level3 알고리즘 탐욕법(Greedy)

알고리즘 문제풀이

목록 보기

5/28

TIL (2022.02.09)

➕ 오늘 푼 문제

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

➕ 아이디어

크루스칼 알고리즘

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘
최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘
- 최소 비용 신장 트리에서는 사이클이 발생하면 안됩니다. 애초에 모든 노드를 이어 붙이기만 하면 되는데 사이클이 발생할 이유가 없습니다.
구현 방법
1. 정렬된 순서에 맞게 그래프에 포함시킵니다.
2. 포함시키기 전에는 사이클 테이블을 확인합니다.
3. 사이클을 형성하는 경우 간선을 포함하지 않습니다.
  1. 사이클 형성 여부는 Union-find 알고리즘으로 확인할 수 있습니다.
시간 복잡도
- 크루스칼 알고리즘 = 정렬 알고리즘 + Union-Find 알고리즘
- 사실상 정렬 알고리즘의 시간 복잡도를 따른다고 봐도 무방하다.

문제 해결 방법

크루스칼 알고리즘을 이용하여, 최소 비용을 구한다
1. 간선을 비용 기준으로 정렬한다.
2. 모든 간선을 탐색하면서 사이클이 발생하는지 확인한다 (find_parent)
3. 사이클이 발생하지 않는다면, 부모를 합치고(union_parent) 비용을 추가한다.

➕ Java 코드

import java.util.*;

class Solution {
    public int findParent(int[] parent, int x){
        if(parent[x] != x){
            parent[x] = findParent(parent, parent[x]);
        }
        return parent[x];
    }

    public void unionParent(int[] parent, int a, int b){
        a = findParent(parent, a);
        b = findParent(parent, b);

        if(a < b){
            parent[b] = a;
        }else{
            parent[a] = b;
        }
    }

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

        // 사이클 테이블 초기화
        for(int i=0; i<n; i++){
            parent[i] = i;
        }

        // 비용순으로 정렬
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2]));

        for(int i=0; i<costs.length; i++){
            int a = costs[i][0];
            int b = costs[i][1];
            int c = costs[i][2];

            if(findParent(parent, a) != findParent(parent, b)){
                unionParent(parent, a, b);
                answer += c;
            }

        }
        return answer;
    }
}

➕ Python 코드

def find_parent(parent, x):
    if parent[x] != x:
        # 루트 노드가 아니라면 재귀적으로 탐색한다
        parent[x] = find_parent(parent, parent[x])

    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    # 더 작은 값을 공통의 루트로 잡는다
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution(n, costs):
    answer = 0
    parent = [i for i in range(n)]

    costs.sort(key=lambda x:x[2])   # 비용 순서대로 간선을 정렬한다

    for a, b, c in costs:
        # 모든 간선을 탐색하며 사이클이 발생하는지 확인한다
        if find_parent(parent, a) != find_parent(parent, b):
            # 사이클이 발생하지 않는다면, union을 진행하고 비용을 추가한다
            union_parent(parent, a, b)
            answer += c

    return answer