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

오늘 풀어볼 문제는 ⭐ 섬 연결하기 이다!

해당 문제는 너무 기본적인 크루스칼 문제였다.

1. 접근법

크루스칼 알고리즘이다. 크루스칼 알고리즘은 무엇인까! 최소 신장 트리의 대표적 알고리즘이라고 생각하면 된다.

1. 거리가 짧은 순으로 정렬한다.
2. 사이클의 생성 여부를 union-find로 확인하고, 생성되지 않는다면 answer에 합해주면 된다.

말은 간단하지만, union-find가 기억나지 않는다면 참사가 날 수 있다.(바로 나처럼)

2. 코드

import java.util.*;
import java.io.*;

class Solution {
    
    static class Info implements Comparable<Info> {
        int from;
        int to;
        int d;
        
        public Info(int from, int to, int d) {
            this.from=from;
            this.to=to;
            this.d=d;
        }
        
        @Override
        public int compareTo(Info o) {
            return this.d-o.d;
        }
    }
    
    static Queue<Info> pq=new PriorityQueue<>();
    static int parent [];
    
    public int solution(int n, int[][] costs) {
        parent=new int[n];
        int answer=0;
       
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        for (int[] cost : costs) {
            int s = cost[0];
            int e = cost[1];
            int d = cost[2];
            pq.add(new Info(s, e, d));
    }
         
        while(!pq.isEmpty()) {
            Info now = pq.poll();
            if(!union(now.to, now.from)) continue;
            answer +=now.d;
        }
        
        return answer;
    }
    
    public static boolean union (int to, int from) {
        
        if(find(to)==find(from)) return false;
        
        else if(find(to)>find(from)) parent[to]=from;
        else parent[from]=to; 
    
        return true;
    }
    
    public static int find(int target) {
        if(parent[target]==target) return target;
        return parent[target] = find(parent[target]);
    }
}

다음과 같은 코드!!!

참고로 find 함수에서 중간 경로들도 값을 갱신해주는 걸 잊어선 안된다.

해당 코드는 union에서 큰 에러를 맞이하고 있다. 왜 그런가?

    public static boolean union (int to, int from) {
        
        if(find(to)==find(from)) return false;
        
        else if(find(to)>find(from)) parent[to]=from;
        else parent[from]=to; 
    
        return true;
   }

당연히 틀리게 된다!!! 현재 부모(=root 노드) 갱신이 아주 잘못되고 있다.

위와 같이 부모노드를 갱신해주게 되면, 다음과 같은 뜻이 된다.

내 루트 노드 값이 뭐든 상관없이, 바로 내 윗노드(=부모노드)의 값을 갱신

1, 3, 5 라는 노드가 있고, 현재 1->3 까지 진행되었다고 가정한다. 새로운 노드 5는 3의 하위 노드로써 들어가야 하는 상황이다. 그러나 내 코드는 위와 같은 상황에서 값을 제대로 갱신하지 못한다.

모든 1, 3, 5는 루트 노드인 1을 부모값으로 가져야 하지만, 내 코드는 5의 부모값을 그저 3으로 갱신하고 멈춘다.

즉 코드는 다음과 같이 바뀌어야 한다.

public static boolean union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa == pb) return false;
    parent[pa] = pb;
    return true;
}