[코딩테스트] Java 섬 연결하기

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

가장 최소의 코스트로 모든 다리를 연결하여야 하므로 최소 신장 트리를 구하는 문제입니다.

최소 신장 트리를 구하기 위한 크루스칼 알고리즘을 활용하여 문제를 풀어줍니다.

소스코드

import java.util.*;

class Solution {
    
    class Bridge implements Comparable<Bridge> {
        int src, dest, cost;
        
        public Bridge(int src, int dest, int cost) {
            this.src = src;
            this.dest = dest;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Bridge b) {
            if(this.cost == b.cost) {
                return this.src - b.src;
            }
            return this.cost - b.cost;
        }
    }
    int[] parents;
    
    public int findParent(int n) {
        if (parents[n] != n) {
            parents[n] = findParent(parents[n]);
        }
        return parents[n];
    }
    
    public void union(int a, int b){
        a = findParent(a);
        b = findParent(b);
        
        if (a < b) {
            parents[b] = a;
        } else {
            parents[a] = b;
        }
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int len = costs.length;
        List<Bridge> bridges = new ArrayList<>();
        
        for(int i = 0; i < len; i++){
            Bridge newBridge = new Bridge(costs[i][0], costs[i][1], costs[i][2]);
            bridges.add(newBridge);
        }
        Collections.sort(bridges);
        parents = new int[n+1];
        for(int i = 0; i <= n; i++) {
            parents[i] = i;
        }
        
        for(Bridge bridge: bridges) {
            if (findParent(bridge.src) != findParent(bridge.dest)) {
                union(bridge.src, bridge.dest);
                answer += bridge.cost;
            }
        }
        
        return answer;
    }
}

코드 설명

• Bridge 클래스
  섬 간의 다리를 나타내는 클래스입니다.
  • src: 다리의 출발 섬.
  • dest: 다리의 도착 섬.
  • cost: 다리의 건설 비용.
  • Comparable 인터페이스를 구현하여, 비용이 낮은 순서대로 정렬되도록 합니다. 비용이 같을 경우 src의 값을 기준으로 정렬됩니다.
• findParent 메서드
  findParent는 주어진 노드 n의 대표 부모 노드를 찾는 재귀 메서드입니다.
  • 경로 압축(Path Compression) 기법을 사용하여, 트리의 높이를 줄이고 효율성을 높입니다.
• union 메서드
  • 두 노드 a와 b를 하나의 집합으로 합칩니다. 두 집합의 대표 부모를 찾은 후, 더 작은 번호의 노드가 부모가 되도록 합니다.
  • 이를 통해, 서로 다른 집합을 병합하면서 트리 구조를 형성합니다.
• Solution 메서드
  • Bridge 객체 리스트 bridges에 다리 정보를 추가하고 비용 순으로 정렬합니다.
  • parents 배열을 초기화하여 각 섬의 부모를 자기 자신으로 설정합니다.
  • for 반복문을 통해 비용이 낮은 다리부터 탐색하여, 두 섬이 다른 집합에 속해 있을 경우 union 연산을 수행하고 다리 비용을 answer에 더합니다.
  • 최소 비용으로 모든 섬을 연결할 수 있는 다리들의 총 비용을 answer로 반환합니다.