크루스칼 알고리즘

---

최소 신장 트리

• 가중치 무방향 그래프에서 모든 정점을 최소 비용으로 연결할 수 있는 방법
  • 가중치 무방향 그래프: 간선에 가중치가 있고 방향이 없는 그래프
• 그래프 위 모든 정점을 최소 비용으로 탐색하는 방법 찾기 위함
• 최소 비용이 되려면 사이클을 형성하지 않아야 함
• 최소 신장 트리 찾는 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 있음

크루스칼 알고리즘이란

• 간선을 기준으로 트리 형성
• 가중치가 작은 간선부터 선택
• 사이클 발생 경우를 알아야 함
  : 같은 그래프에 속한 두 노드를 연결했을 때
  ➡ Union Find를 통해 판별
  

Union Find

• 합집합 찾기
• 두 원소가 같은 집합에 속하는지 판별하는 방법

참고링크(그림설명👍)

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

 	public int solution(int n, int[][] costs) {

        // 크루스칼 알고리즘 사용하기 위해 가중치 기준 정렬
        Arrays.sort(costs, (int[] c1, int[] c2) -> c1[2] - c2[2]);

        // union 사용위해 부모 배열 선언
        int[] parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i; // 자기 자신으로 초기화

        int answer = 0;
        for (int i = 0; i < costs.length; i++) {
            int from = costs[i][0];
            int to = costs[i][1];
            int cost = costs[i][2];

            int fromP = findParent(parent, from);
            int toP = findParent(parent, to);

            if (fromP == toP)
                continue; // 서로 부모노드가 같을때 (=사이클 생성) 패스
            answer += cost; // 다리 생성 (연결)
            union(parent, fromP, toP); // 연결했으니까 부모 노드 갱신

        }
        return answer;
    }

부모 찾는 메소드

	static int findParent(int[] parent, int node) {
        if (parent[node] == node)
            return node; // 부모노드가 자기자신일때
        return findParent(parent, parent[node]); // 루프노드 찾을때까지
    }

부모 노드 갱신 메소드

	public void union(int[] parent, int node1, int node2) { 
    	// 숫자가 더 작은 노드가 부모노드로
        if (node1 < node2)
            parent[node2] = node1;
        else
            parent[node1] = node2;
    }