Coding Test/Programmers

[Lv.3] 섬 연결하기 [프로그래머스_코딩테스트] [MST, Greedy, UnionFind, Kruskal]

whawoo 2025. 5. 17. 17:05
반응형

🔍 문제 요약

https://school.programmers.co.kr/learn/courses/30/lessons/42861

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

해당 문제는 각 섬을 하나로 연결하는 최소 비용을 구하는 문제로 costs는 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 와 같은 식으로 주어지고 n개의 섬을 연결해야 한다. (cost는 섬 1, 섬 2, 비용 이런식으로 3개의 데이터가 하나의 묶음으로 연결)

 

🧠 나의 접근 방식과 시행착오

일단 익숙치 않았던 MST 문제를 해결하는 거에 대해서 시간이 걸려서 해결은 역시 제대로 안 된 상태. 필자가 푸려고 시도 했던 방식은 아래까지이다. 리스트에 costs를 집어넣고 비용 순으로 오름차순하게 정렬 후 하나씩 넣어가면서 순환되지 않게 하나로 연결하는 방법. 그렇지만 정렬까지는 생각했었지만 그 이후의 구조를 어떤 식으로 구현할 지 감이 잘 안 왔었기에 바로 풀이과정을 보고 공부를 좀 더 하기로 하였다.

public int solution(int n, int[,] costs) {
        // 섬 연결 (a, b, cost) 리스트
        var islandLinkList = new List<(int, int, int)>();
        
        for (int i = 0; i < costs.GetLength(0); i++)
        {
            islandLinkList.Add((costs[i, 0], costs[i, 1], costs[i, 2]));
        }
        
        // 비용이 적은 것들부터 오름차순 시켜보자.
        islandLinkList.Sort((a, b) => a.Item3.CompareTo(b.Item3));
        
        int answer = 0;
        
        // 문제의 접근 방식?
        // 핵심은 각 경로를 하나씩 넣어보면서 순환하지 않고 모든 지점이 연결이 되는 최소 비용을 구하기
        // islandLinkList 를 돌면서 찾기?
        
        return answer;
    }

 

✅ 풀이 코드

풀이는 kruskal 방식을 사용해서 MST 문제를 해결한다.

🎯 MST(Minimum Spanning Tree)란?

  • 모든 노드를 연결하면서
  • 사이클이 없고,
  • 전체 간선 비용의 합이 최소인 그래프

✅ 어떻게 풀어야 하는가? → 대표적인 두 가지 알고리즘

  알고리즘핵심  아이디어특징
크루스칼 (Kruskal) 간선을 비용순 정렬 후, 순서대로 연결. 사이클이 생기면 제외 ✨ Union-Find 필요
프림 (Prim) 하나의 노드부터 시작 → 가장 적은 비용의 이웃 노드를 하나씩 연결 우선순위 큐 필요

 

1. 모든 간선(섬1, 섬2, 비용)을 비용 오름차순으로 정렬한다.
2. 각 섬을 Union-Find로 관리한다 (처음엔 다 따로 그룹).
3. 비용이 낮은 간선부터 하나씩 연결해본다.
   → 이미 같은 그룹이면 무시 (사이클 생김)
   → 아니면 연결 + 비용 누적
4. 모든 섬이 하나의 그룹이 될 때까지 반복한다.

 

gpt를 통해서 문제의 풀이를 얻어낸 것으로 초반의 1,2번까지는 동일하게 구조가 되어있다. 여기서 중요한 점은 3,4번의 과정이다. Union-Find를 적용하기 위해 먼저 parent에 각 섬의 번호로 초기화를 시킨다. 그 후 비용이 작은 섬부터 순서대로 parent가 다른 경우 하나로 Union시키는 과정을 돌린다. 그 후 connected가 n-1이 되는 순간 (하나로 섬들이 연결된 순간) 까지 cost를 더하고 결과를 도출. 실제로 문제를 보면 Union-Find를 쓸 줄 알면 문제를 쉽게 해결할 수 있었지 않았나 싶긴 하다. 다만 그게 늘 그렇지만 익숙치 않아서인지 좀 더 연습이 필요할 듯 하다. (보면 바로 적용 가능할 수 있게..)

using System;
using System.Collections.Generic;

public class Solution {
    int[] parent;

    public int solution(int n, int[,] costs) {
        // 1. 간선을 리스트로 변환
        var edges = new List<(int a, int b, int cost)>();
        for (int i = 0; i < costs.GetLength(0); i++) {
            edges.Add((costs[i, 0], costs[i, 1], costs[i, 2]));
        }

        // 2. 비용 기준으로 정렬
        edges.Sort((x, y) => x.cost.CompareTo(y.cost));

        // 3. Union-Find 초기화
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        int totalCost = 0;
        int connected = 0;

        // 4. MST 생성
        foreach (var (a, b, cost) in edges) {
            if (Find(a) != Find(b)) {
                Union(a, b);
                totalCost += cost;
                connected++;

                if (connected == n - 1) break; // MST 완성
            }
        }

        return totalCost;
    }

    int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]);
        return parent[x];
    }

    void Union(int a, int b) {
        int rootA = Find(a);
        int rootB = Find(b);
        if (rootA != rootB) parent[rootB] = rootA;
    }
}

 

🔄 정리

kruskal 방식을 사용해서 MST 문제를 해결하는 핵심적인 문제로 보인다. 이러한 문제의 유형은 사실 자주 나오는 케이스다 보니 익숙해질 수 있게 Union-Find 방법을 공부해두어야 할 것.

반응형