크루스칼 알고리즘
최소 신장 트리
- 가중치 무방향 그래프에서 모든 정점을 최소 비용으로 연결할 수 있는 방법
가중치 무방향 그래프
: 간선에 가중치가 있고 방향이 없는 그래프
- 그래프 위 모든 정점을 최소 비용으로 탐색하는 방법 찾기 위함
- 최소 비용이 되려면
사이클
을 형성하지 않아야 함
- 최소 신장 트리 찾는 알고리즘은
크루스칼 알고리즘
과 프림 알고리즘
이 있음
크루스칼 알고리즘이란
간선
을 기준으로 트리 형성
- 가중치가 작은 간선부터 선택
사이클 발생 경우
를 알아야 함
: 같은 그래프에 속한 두 노드를 연결했을 때
➡ Union Find
를 통해 판별
Union Find
- 합집합 찾기
- 두 원소가 같은 집합에 속하는지 판별하는 방법
참고링크(그림설명👍)
프로그래머스 : 섬 연결하기
public int solution(int n, int[][] costs) {
Arrays.sort(costs, (int[] c1, int[] c2) -> c1[2] - c2[2]);
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;
}