신장 트리 : 모든 임의의 정점이 연결된 그래프인 연결 그래프의 부분 그래프, 모든 정점이 간선으로 연결되어 있지만 사이클이 존재하지 않는 그래프
최소 신장 트리
신장 트리를 구성하는 간선들의 가중치 합이 가장 작은 신장 트리, 최소 신장 트리를 구현하는 알고리즘은 주로 2가지(크루스칼, 프림)가 있다.
👀 크루스칼 알고리즘
최소 신장 트리 구현에 사용되는 알고리즘으로 가중치 그래프의 모든 간선들을 대상으로
1) 최소 비용의 간선으로 구성
2) "사이클을 형성하지 않음"
위 조건을 지켜가며 각 단계마다 사이클을 이루지 않는 최소 비용 간선을 선택하여 최소 신장 트리를 완성하는 알고리즘
위 순서대로(간선의 비용이 적은 순서대로) 선택하여 모든 노드가 연결되면 종료한다.
매 단계마다 최선의 해를 선택하기에 그리디 알고리즘에 바탕을 두고있으며
서로소 집합(Disjoint Set), 유니온 파인드(Union-Find)을 알아야 알고리즘을 올바르게 구현할 수 있다.
🧐 서로소 집합이란?
공통 원소가 없는 두 집합을 의미
서로소 집합은 트리 자료구조를 통해 집합을 표현하고, 연산을 수행
하나의 트리를 하나의 집합으로 볼 때, find연산은 트리의 루트노드를 찾고, 그 루트노드를 통해 특정 집합을 표현
그리고 union 연산의 경우 두 원소에 대해 find 연산을 수행하여 각각의 루트노드를 찾고,
한 쪽의 루트노드를 다른 쪽에 연결함으로써 하나의 트리로 만드는 합집합 연산을 수행
👀 유니온 파인드
상호 배타적 집합(Disjoint-set)
▷ 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
▷ 2가지 연산으로 이루어져 있음.
-
Find : x가 어떤 집합에 포함되어 있는지 찾는 연산
-
Union : x와 y가 포함되어 있는 집합을 합치는 연산
코드 예시
class Solution {
static int[] parent;
/* A가 속한 집합, B가 속한 집합을 합침.
1) A와 B의 루트 노드 A',B'를 각각 찾는다
2) A'를 B'의 부모 노드로 설정한다 */
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) parent[b] = a;
}
// x가 속한 루트 노드 값을 반환, 즉 x가 어느 집합에 속해있는지 확인
public static int find(int x) {
if (x == parent[x])
return x;
else
return parent[x] = find(parent[x]);
}
}💻 코딩테스트 연습 문제
(크루스칼 알고리즘 사용 예 - 프로그래머스 [섬 연결하기])
문제
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때,
최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다.
예를 들어 A 섬과 B 섬 사이에 다리가 있고,
B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
**제한사항**
섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고,
costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다.
즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다.
이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.코드 풀이
import java.util.Arrays;
class Solution {
static int[] parent; //부모 노드 담을 배열
public int solution(int n, int[][] costs) {
int answer = 0;
parent = new int[n];
//다리 연결 비용 내림차순 정렬
Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2]));
//부모노드 초기화
for(int i=0; i<n; i++){
parent[i] = i;
}
//A섬, B섬이 연결되어있는지 찾아서 비용 반환
for(int[] cost : costs){
if(find(cost[0]) != find(cost[1])) {
answer += cost[2];
union(cost[0], cost[1]);
}
}
return answer;
}
//유니온 (a를 b의 부모 노드로 설정)
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) parent[b] = a;
}
//x가 속한 루트 노드 값을 반환
public static int find(int x) {
if (x == parent[x])
return x;
else
return parent[x] = find(parent[x]);
}
}
프로그래머스 - 섬 연결하기 (탐욕법)
https://programmers.co.kr/learn/courses/30/lessons/42861
