MST
- 모든 노드를 연결하면서 총 가중치를 최소화하는 것
- 가장 최적의 선택을 하는 것
예시
- 도로 건설: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
- 전기 회로: 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
- 통신: 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
- 배관: 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제
Kruskal 알고리즘
이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법
- 대표적인 그리디 알고리즘
- 간선 중심의 알고리즘
서로소 집합
- 처음에 각 정점은 자기 자신을 부모로 설정(서로소)
- 두 정점이 선택되는 순간 합집합
- 부모-자식 관계가 생김
- 결과적으로 같은 패밀리가 되면 모두 선택되었다는 의미 ➡️ Kruskal에서 사이클 판단 유무로 사용
package graph;
public class 서로소 {
static int[] p;
// 각 원소의 부모를 자기 자신으로 초기화하는 메서드 (서로소 집합 완성)
static void makeSet(int V) {
p = new int[V];
for (int i = 0; i < V; i++) {
p[i] = i;
}
}
// 원소의 루트 부모를 찾는 메서드
static int find(int e) {
// 경로 압축을 통해 트리의 높이를 줄임
if(e != p[e]) {
p[e] = find(p[e]); // 재귀적으로 더 높은 부모를 찾음
}
return p[e];
}
// 두 원소를 결합하는 메서드 (합집합 수행)
static boolean union(int f, int t) {
// 각 원소의 루트 부모를 찾음
int fp = find(f);
int tp = find(t);
// 같은 부모를 가지는 경우, 결합 X
if(fp == tp) return false;
// 두 집합을 결합: t의 부모를 f의 부모로 설정
p[tp] = fp; // t의 부모의 부모를 설정하는 이유? 집합 관계가 안흐트러지고 유지하기 위함
return true;
}
public static void main(String[] args) {
// 5개의 원소(0, 1, 2, 3, 4)로 집합을 초기화
makeSet(5);
// 원소 0과 1을 결합
union(0, 1);
// 원소 1과 2를 결합
union(1, 2);
// 원소 3과 4를 결합
union(3, 4);
// 원소 0의 루트 부모를 찾음 (0, 1, 2는 같은 집합)
System.out.println("Root of 0: " + find(0)); // 출력: Root of 0: 0
// 원소 1의 루트 부모를 찾음
System.out.println("Root of 1: " + find(1)); // 출력: Root of 1: 0
// 원소 2의 루트 부모를 찾음
System.out.println("Root of 2: " + find(2)); // 출력: Root of 2: 0
// 원소 3의 루트 부모를 찾음
System.out.println("Root of 3: " + find(3)); // 출력: Root of 3: 3
// 원소 4의 루트 부모를 찾음
System.out.println("Root of 4: " + find(4)); // 출력: Root of 4: 3
// 원소 0과 3의 루트 부모를 비교하여 서로 다른 집합인지 확인
System.out.println("Are 0 and 3 in the same set? " + (find(0) == find(3))); // 출력: false
// 원소 2와 3을 결합
union(2, 3);
// 결합 후 다시 루트 부모를 확인
System.out.println("Root of 3 after union with 2: " + find(3)); // 출력: Root of 3: 0
System.out.println("Are 0 and 3 in the same set now? " + (find(0) == find(3))); // 출력: true
}
}
Kruskal 방법
- 그래프의 간선들을 가중치의 오름차순으로 정렬
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
- 즉, 가장 낮은 가중치를 먼저 선택
- 사이클을 형성하는 간선을 제외(union()이 false이면 이미 같은 집합이므로 사이클이 있다고 간주)
- 해당 간선을 현재의 MST의 집합에 추가
- 위의 과정을 (V - 1)개의 간선을 가질 때까지 반복
/*
Q. 모든 정점을 연결하는 최소 비용을 구하라(ex.모든 도시를 여행하는 최소 비용을 구하라)
첫째줄:정점 개수
둘째줄:간선 개수
나머지:간선 정보
7
11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
*/
package graph;
import java.util.Arrays;
import java.util.Scanner;
public class Kruskal {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt();
int E = sc.nextInt();
Edge[] arr = new Edge[E];
for (int i = 0; i < E; i++) {
int f = sc.nextInt();
int t = sc.nextInt();
int w = sc.nextInt();
arr[i] = new Edge(f, t, w); // (2)
}
// 가중치로 정렬
Arrays.sort(arr); // (3)
// 서로소 집합 만들기
makeSet(V); // (4)
// 사이클이 없는 간선들을 선택하며 가중치 최소 비용 구하기
int result = 0; // (5)
int pickCnt = 0; // (6)
for(Edge e:arr) { // (7)
if(union(e.f, e.t)) {
result += e.w;
if(++pickCnt == (V-1)) break; // (정점 개수 - 1)개가 선택될 때까지만 반복
}
}
System.out.println(result);
sc.close();
}
static int[] p;
// 각 원소의 부모를 자기 자신으로 초기화하는 메서드 (서로소 집합 완성)
static void makeSet(int V) {
p = new int[V];
for (int i = 0; i < V; i++) {
p[i] = i;
}
}
// 원소의 루트 부모를 찾는 메서드
static int find(int e) {
// 경로 압축을 통해 트리의 높이를 줄임
if(e != p[e]) {
p[e] = find(p[e]); // 재귀적으로 더 높은 부모를 찾음
}
return p[e];
}
// 두 원소를 결합하는 메서드 (합집합 수행)
static boolean union(int f, int t) {
// 각 원소의 루트 부모를 찾음
int fp = find(f);
int tp = find(t);
// 같은 부모를 가지는 경우, 결합 X
if(fp == tp) return false;
// 두 집합을 결합: t의 부모를 f의 부모로 설정
p[tp] = fp;
return true;
}
static class Edge implements Comparable<Edge> { // (1)
int f, t, w;
public Edge(int f, int t, int w) {
super();
this.f = f;
this.t = t;
this.w = w;
}
@Override
public String toString() {
return "Edge [f=" + f + ", t=" + t + ", w=" + w + "]";
}
// 가중치 정렬을 위해 Comparable implements 하여 정렬
@Override
public int compareTo(Edge o) {
return Integer.compare(w, o.w);
}
}
}
Prim 알고리즘
- 대표적인 그리디 알고리즘
- 정점 기반 알고리즘
- 간선이 많으면 Kruskal에서는 정렬에 시간이 많이 듬 ➡️ 정점 기반 처리를 하는 Prim 사용 (😉 간적크간만프)
- 주어진 간선 수가 2500 이하이면 Kruskal, 그 이상이면 Prim
Prim 방법
1. 시작 단계에서는 시작 정점만이 MST 집합에 포함
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선(PriorityQueue 활용하면 쉬움)으로 연결된 정점을 선택하여 트리를 확장, 선택된 정점들의 인접 정점도 포함하여 계속 반복
3. 모든 정점이 선택되었으면 끝냄.
/*
Q. 모든 정점을 연결하는 최소 비용을 구하라(ex.모든 도시를 여행하는 최소 비용을 구하라)
첫째줄:정점 개수
둘째줄:간선 개수
나머지:간선 정보
7
11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
*/
package graph;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Prim {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt();
int E = sc.nextInt();
// 2차원 배열에 가중치 저장
int[][] arr = new int[V][V]; // (1)
for (int i = 0; i < E; i++) {
int f = sc.nextInt();
int t = sc.nextInt();
int w = sc.nextInt();
arr[f][t] = arr[t][f] = w;
}
// 정점 방문 유무 확인
boolean[] visited = new boolean[V]; // (2)
int result = 0; // (3)
int pickCnt = 0; // (4)
PriorityQueue<Edge> pq = new PriorityQueue<>(); // (5)
pq.offer(new Edge(0, 0, 0));
while (!pq.isEmpty()) {
Edge e = pq.poll(); // 가장 작은 가중치를 가진 Edge 객체가 나옴
if (visited[e.t]) continue;
visited[e.t] = true;
result += e.w;
if(++pickCnt == V) break;
for (int i = 0; i < V; i++) {
if (!visited[i] && arr[e.t][i] != 0) {
pq.offer(new Edge(e.t, i, arr[e.t][i])); // 선택된 정점으로부터 파생되는 정점들을 큐에 포함
}
}
}
System.out.println(result);
sc.close();
}
static class Edge implements Comparable<Edge> {
int f, t, w;
public Edge(int f, int t, int w) {
super();
this.f = f;
this.t = t;
this.w = w;
}
@Override
public String toString() {
return "Edge [f=" + f + ", t=" + t + ", w=" + w + "]";
}
// 가중치 정렬을 위해 Comparable implements 하여 정렬
@Override
public int compareTo(Edge o) {
return Integer.compare(w, o.w);
}
}
}
다익스트라 알고리즘
가중치가 있는 그래프에서 정점간의 최단 경로를 찾는 방법
- 대표적인 그리디 알고리즘
- Prim 알고리즘과 비슷하지만 현재 정점까지의 최소 비용을 저장할 배열이 필요
다익스트라 방법
- 시작 정점으로부터의 거리를 초기화. 시작 정점의 거리는 0으로 설정하고, 나머지 정점의 거리는 무한대로 설정
- 방문하지 않은 정점 중에서 가장 짧은 거리를 가진 정점을 선택(PriorityQueue를 이용하면 쉬움)
- 선택한 정점과 연결된 인접 정점들의 거리를 업데이트. 즉, 선택한 정점을 거쳐 가는 경로가 더 짧다면 그 거리로 갱신한다는 것. 이 과정을 모든 정점이 방문될 때까지 반복
/*
Q. 출발지 정점에서 도착지 정점까지 연결하는 최소 비용을 구하라
첫째줄:정점 개수
둘째줄:시작정점 종료정점
셋째줄:간선 개수
나머지:간선 정보
7
0 4
11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
*/
package graph;
import java.util.PriorityQueue;
import java.util.Scanner;
public class 다익스트라 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt();
int startV = sc.nextInt();
int endV = sc.nextInt();
int E = sc.nextInt();
// 2차원 배열에 가중치 저장
int[][] arr = new int[V][V];
for (int i = 0; i < E; i++) {
int f = sc.nextInt();
int t = sc.nextInt();
int w = sc.nextInt();
arr[f][t] = arr[t][f] = w;
}
// 정점 방문 유무 확인
boolean[] visited = new boolean[V];
int[] minDistance = new int[V];
for(int i = 0; i < V; i++) {
minDistance[i] = Integer.MAX_VALUE;
}
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.offer(new Edge(startV, startV, 0));
minDistance[startV] = 0;
while (!pq.isEmpty()) {
Edge e = pq.poll();
if (visited[e.t]) continue;
visited[e.t] = true;
if(e.t == endV) break;
for (int i = 0; i < V; i++) {
if (!visited[i] && arr[e.t][i] != 0 && minDistance[i] > (e.w + arr[e.t][i])) {
minDistance[i] = e.w + arr[e.t][i];
pq.offer(new Edge(e.t, i, arr[e.t][i])); // 선택된 정점으로부터 파생되는 정점들을 큐에 포함
}
}
}
System.out.println(minDistance[endV]);
sc.close();
}
static class Edge implements Comparable<Edge> {
int f, t, w;
public Edge(int f, int t, int w) {
super();
this.f = f;
this.t = t;
this.w = w;
}
@Override
public String toString() {
return "Edge [f=" + f + ", t=" + t + ", w=" + w + "]";
}
// 가중치 정렬을 위해 Comparable implements 하여 정렬
@Override
public int compareTo(Edge o) {
return Integer.compare(w, o.w);
}
}
}
🌟 스터디 MST 문제 다익스트라 문제로 바꿔보기
1. 우주 정거장 건설 문제
우주 탐사선들이 정거장을 세우기 위해 N개의 행성에 기지를 건설하려 한다.
각 행성은 (x, y) 좌표를 가지며, 두 행성을 연결하는 비용은 유클리드 거리로 정의된다.
1번 행성에서 다른 모든 행성으로 가는 최소 비용을 구하라.
2. 글로벌 해저 케이블 네트워크 구축 문제
한 글로벌 통신 회사가 N개의 대륙(정점)을 연결하는 M개의 해저 광케이블(간선) 후보를 조사했다.
각 해저 케이블은 특정 두 대륙을 연결하며, 설치 비용이 다르다.
주어진 출발지 대륙에서 목적지 대륙까지 가는 최소 비용을 구하라.
728x90
반응형
'LG 유플러스 유레카 SW > Algorithm' 카테고리의 다른 글
| [#22] 백트래킹 + 위상 정렬 (1) | 2025.02.25 |
|---|---|
| [#20] 알고리즘 - 최단 경로 (0) | 2025.02.21 |
| [#19] 비선형 자료구조 - 그래프 (0) | 2025.02.20 |
| [#18] 비선형 자료구조 - 트리 (0) | 2025.02.19 |
| [#17] 순열 & 조합 & 부분집합 (0) | 2025.02.18 |