99클럽 코테 스터디 14일차 TIL 섬연결하기 (서로소 집합) 자바(Java)

 

 

 

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

프로그래머스

 

오늘 부터 스터디에서 미들러 등급으로 문제를 풀다가 챌린저 문제를 풀어야겠다고 생각해 풀려했다.

하지만 고민에 고민을 하다 시간이 가버려 발표자분의 풀이 방식을 듣게 되었다.

 

 

n -1 개의 다리를 골라야 한다는 것과 제일 비용이 작은 다리를 오름차순 해놓고 고른다는 것까지는 생각이 같았으나 

 

차이점은 union find라는 알고리즘을 사용하는 것이었는데

 

이는 인터넷으로 설명을 들은 뒤 이해를 하고 코드를 작성하게 되었다.

 

https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)

 

위의 유명하신 동빈나님의 블로그에서 공부하였다.

합집합 찾기, 서로소 집합, union-find라 불리는 알고리즘으로 요약하자면 각 노드마다 어디에 속해있는지에 대한 배열을 만들고 관리하는 것이다.

 

1과 2가 연결된다면 둘중 하나의 부모 배열의 값을 작은 노드의 값으로 바꿔준다.(일반적으로 작은 노드의 값)

 

이를 반영하여 코드를 작성하여

import java.util.Comparator;
import java.util.Arrays;

class Solution {
    public int getParent(int parent[], int x) {
		if(parent[x] == x) return x;
		return parent[x] = getParent(parent, parent[x]);
	}
	public void unionParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if(a < b) parent[b] = a;
		else parent[a] = b;
	}
	public boolean findParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		
		if( a==b) {
			return true;
		}
		else {
			return false;
		}
	}
	
	public int solution(int n, int[][] costs) {
		//[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
		int answer = 0;
		int[] parent = new int[n];
        for(int i = 0; i < parent.length; i++){
            parent[i] = i;
        }
        
        Arrays.sort(costs, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
		
		for(int i = 0; i< costs.length; i++) {
			if(!findParent(parent, costs[i][0], costs[i][1])) {
				answer += costs[i][2];
				unionParent(parent, costs[i][0], costs[i][1]);
			}
		}
		
		

		return answer;
	}

}

 

 

 

 

내일은 다익스트라 알고리즘을 이용한 문제를 풀어봐야겠다.

점점 예전에 알고리즘 문제를 풀던 기억도 돌어와고 실력이 그때보다 늘어가는것 같다.