코딩 테스트 합격자 되기 스터디 5주차 : 집합

집합

집합의 개념

• 순서와 중복이 없는 원소들을 갖는 자료구조상호배타적 집합
• 교집합이 없는 집합관계(집합은 꼭 2개가 아니라 N개일수도 있음)상호배타적 집합의 특성 활용 분야
• 이미지 분할
• 도로 네트워크 구성
• 최소 신장 트리 알고리즘
• 게임 개발
• 클러스터링 작업집합의 연산
• 유니온-파인드 알고리즘
• 집합 알고리즘에 쓰이는 연산
  • 합치기(유니온)
  • 탐색(파인드)파인드 연산특정 노드의 루트 노드가 무엇인지 탐색합치기 연산두 집합을 하나로 합치는 연산

문제

크루스칼 알고리즘

import java.util.*;

class Solution {
    private int[] parent;
    public int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }

    public void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b) {
            parent[b] = a;
        }
    }

    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
        Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);
        //Kruskal Algorithm
        for(int i = 0; i < costs.length; i++) {
            if(find(costs[i][0]) != find(costs[i][1])) {
                union(costs[i][0], costs[i][1]);
                answer += costs[i][2];
            }
        }
        return answer;
    }
}

출처

코딩 테스트 합격자 되기 - C++