Today I Learned

오늘은 지난 주에 배웠던 MST 문제를 한 번 풀어봤다.

섬 연결하기

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

• 문제

  n개의 섬과 n개의 섬을 서로 연결할 수 있는 다리와 그 비용이 제시된다. 최소 비용으로 모든 섬을 연결할 때의 비용을 반환해라.

• 풀이 과정

1. 전형적인 MST 문제이고 다리의 개수에 제약조건이 있으므로 크루스칼로 풀면 될 것이라 생각했다.

2. 우선 크루스칼 알고리즘으로 풀려면 사이클 형성 여부를 판단할 유니온 파인드 알고리즘부터 구현해야 했다.
   먼저 자신의 루트 노드를 담는 int 배열을 하나 만들고 자기 자신의 값으로 초기화해둔다.(아직 아무 연결이 안되어있으니까)

3. find 함수는 경로단축으로 간단하게 구현해두고 union 함수는 서로 루트가 같으면 사이클이 형성되므로 바로 return;시켜 종료하고 서로 루트가 다를때만 연결하도록 했다.

4. 크루스칼의 적용을 위해 costs[?][2]의 값을 기준으로 이차원배열 costs를 오름차순으로 정렬한다. 이 때 Arrays.sort(costs, Comparator.comparingInt(a->a\[2]));로 간단하게 정렬이 가능하다.

5. 이제 정렬된 costs 다리 배열을 순회하면서 최소 비용의 다리부터 union 메서드로 연결시킨다. (union 안에서 사이클이 형성되는건 자동으로 연결시키지 않는다.) count 변수를 둬서 다리가 n-1개가 설치되면 for문을 break 시켜 시간을 단축시키게 했다.

• 헤멨던 부분
  union 메서드 안에서 서로 연결시킬 때,
  root[y] = rootX; 로 했더니 62.5점 밖에 나오지 않았다.
  코드를 한줄 한줄 뜯어보니 이 부분에서 y만 root가 바뀌고 y와 연결된 다른 섬들은 root가 바뀌지 않는다는 것을 알게 되었다.
  그래서 처음엔 for문으로 root배열에서 rootY값을 가진 섬들을 다 바꾸게 코드를 짜서 통과는 했으나 for문으로 한번씩 더 돌린다는건 그만큼 시간복잡도가 늘어난다는 것이기에 좀 더 효율적인 방법을 생각해봤다.
  그래서 생각해낸 것이 root[rootY] = rootX; 로 하면 가장 루트가 되는 노드를 rootX;로 바로 바꾸는 것이니 다른 rootY에 연결된 섬들도 rootY의 루트가 rootX로 바뀌니까 한번에 적용되게 바뀌었다. 이게 원래 유니온파인드의 방식일텐데 내가 잘못 구현하고 있었던 것 같다. 정리하자면 합칠때는 루트노드를 바꿔서 한번에 합쳐야한다는 것이다.

• 최종 답안

import java.util.*;

class Solution {
    
    static int[] root;
    static int answer;
    static int count;
    
    public void union(int x, int y, int cost){
        int rootX = find(x);
        int rootY = find(y);
        
        if(rootX == rootY) return;
        
        root[rootY] = rootX;
        answer += cost;
        count++;
    }
    
    public int find(int x){
        if(root[x] != x){
            root[x] = find(root[x]);
        }
        return root[x];
    }
    
    public int solution(int n, int[][] costs) {
        if(n<=1) return 0;
        
        answer = 0;
        root = new int[n];
        count = 0;
        
        // unionfind 초기화
        for(int i=0; i<n; i++){
            root[i] = i;
        }
        
        // 크루스칼 적용하기 위해 sort
        Arrays.sort(costs, Comparator.comparingInt(a -> a[2]));
        
        // 크루스칼로 MST 구현
        for(int i=0; i<costs.length; i++){
            if(count >= n-1) break;
            int x = costs[i][0];
            int y = costs[i][1];
            int cost = costs[i][2];
            union(x,y,cost);
        }
        
        return answer;
    }
}