문제

Programmers - 섬 연결하기

요약

모든 섬을 연결할 수 있는 전체 간선의 최소 비용

접근

일단 섬들을 연결하는걸 보고 그래프 관련 문제라는 생각이 들었다.

• 처음에 접근한 방식

1. costs를 [0]과 [1]을 기준으로 정렬되도록 만듦
2. costs를 순회하며, 각 노드가 포함된 최소 비용이 드는 경로를 answer에 누적.
3. 방문한 섬들을 visited 처리

이 방식대로 문제를 푸니 전체 섬의 수를 n개라 했을 때, n-1을 순회해야하는데, n을 순회하는 문제가 있었다.

이때 문제 푸는 시간을 1시간 넘게 써서 AI의 도움을 받아 올바르게 접근하고 있는지 물어보니, 이 문제는 MST(최소 신장 트리)를 구현하는 문제였다.

• MST란?
  가중치가 있는 그래프에서 모든 정점을 가장 작은 비용으로 연결하는 트리

알고리즘

MST를 구현하는 알고리즘은 총 2가지 방법이 있다.

1. 크루스칼 알고리즘 (Kruskal)

   : 가중치가 가장 작은 간선부터 순차적으로 탐색하며 하나의 그래프를 완성

2. 프림 알고리즘 (Prim)

   : 임의의 노드를 먼저 방문처리한 후 인접한 노드 중 비용이 낮은 간선을 찾아가며 하나의 그래프를 완성

나는 좀 더 직관적인 크루스칼 알고리즘을 선택해 풀었다.

크루스칼 알고리즘의 핵심 아이디어는 각 노드마다 최상단 조상 노드의 정보를 저장하고, 모든 노드의 최상단 조상 노드를 동일하게 만드는 것이다.

이를 위해서 가장 중요한 것은 Find와 Union이다.
find : 현재 노드의 최상단 조상 노드를 찾는 것
union : 두 노드 그룹을 하나의 노드 그룹으로 합치는 것

find는 재귀로 구현하고,
union은 노드 연결 정보를 순회하며 하나의 간선에 연결된 두 노드의 부모 노드가 다르다면 하나로 합치는게 핵심!

최종 코드

import java.util.Arrays;

class Solution {
    int[] lands;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        // 각 노드의 부모 노드 저장
        lands = new int[n+1];
        for (int i = 0; i < lands.length; i++) {
            // 본인이 부모 노드가 되도록 초기화
            lands[i] = i;
        }
        
        // costs를 cost 기준으로 정렬
        Arrays.sort(costs, (a1, b1) -> a1[2] - b1[2]);
        
        // 2. 메인 로직에서의 Union-Find 적용
        for (int i = 0; i < costs.length; i++) {
            // 1. 각 시작노드와 끝 노드를 뽑는다.
            int start = costs[i][0];
            int end = costs[i][1];
            
            // 각 노드의 부모 노드가 동일한지 확인
            // 2-1. 부모 노드가 동일하다면 skip
            int rootStart = find(start);
            int rootEnd = find(end);
            if (rootStart == rootEnd) continue;
            // 2-2. 부모 노드가 다르다면 두 그룹을 하나로 묶는다.
            else {
                lands[rootEnd] = rootStart;
                
                answer += costs[i][2];
            }
        }
        
        return answer;
    }
    
    // 별도의 find 메서드를 만들어 '최종 대표'를 찾는 로직을 구현
    public int find(int land) {
        // 지금 섬이 최종 끝인지 확인
        if (lands[land] == land) {
            return land;
        }
        
        // 내가 최종 노드가 아니라면, 내 부모의 부모를 찾음
        return find(lands[land]);
    }
}

새로 배운 점

MST라는 걸 개념만 알고 있었는데, 실제로 구현하려니 너무 어려웠다.
크루스칼 알고리즘은 처음 듣고, 프림 알고리즘은 들어만 봤는데, 실제로 마주하니 어렵다..
그래도 이렇게 기록해나가며 문제를 풀다보면 나중엔 쉽게 잘 풀지 않을까라는 생각 중이다.

• 처음에 접근한 방식으로 푼 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        // 이어진 섬들 저장
        boolean[] visited = new boolean[n];
        
        // costs를 cost 기준으로 정렬
        Arrays.sort(costs);
        
        for (int i = 0; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < costs.length; j++) {
                int start = costs[j][0];
                int end = costs[j][1];
                if (start == i || end == i) {
                    // 같은 경우를 처리하는게 관건
                    if (!(visited[start] && visited[end])) {
                        visited[start] = true;
                        visited[end] = true;
                        min = Math.min(min, costs[j][2]);
                        System.out.println(i + " = " +costs[j][0] + " | " +  costs[j][1] + " : " + min);   
                    }
                    // System.out.println(i + " = " +costs[j][0] + " | " +  costs[j][1] + " : " + min);
                }
            }
            answer += min;
        }
        
        return answer;
    }
}