최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.
최소 신장 트리의 특징
사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 수는 항상 N - 1개다.
최소 신장 트리 핵심 이론
1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기
최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다. edge class는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다. 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화한다. 배열의 인덱스를 해당 자리의 값으로 초기화하면 된다.
2. 그래프 데이터를 가중치 기준으로 정렬하기
에지 리스트의 담긴 그래프를 데이터를 가중치 기준으로 오름차순 정렬한다.
3. 가중치가 낮은 에지부터 연결 시도하기
가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다. 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union연산을 이용해 두 노드를 연결한다.
4. 과정 3 반복하기
전체 노드의 개수가 N개이면 연결한 에지의 개수가 N - 1이 될 때까지 과정 3을 반복한다.
5. 총 에지 비용 출력하기
에지의 개수가 N - 1이 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력한다. 최소 신장 트리는 다른 그래프 알고리즘과 달리, 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다. 그 이유는 에지를 기준으로 하는 알고리즘이기 때문이다. 또한 사이클이 존재하면 안 되는 특징을 지니고 있기 때문에 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 된다.
코드로 표현
static int[] parent;
static PriorityQueue<pEdge> que;
노드 수, 에지 수 입력
que = new PriorityQueue<>(); // 자동 정렬을 위해 우선순위 큐 자료구조 선택하기
parent = new int[n + 1];
parent배열 인덱스로 초기화
for(int i = 0; i < M; i++) {
시작 노드 s, 끝 노드 e, 가중치 입력받기 v
que.add(new pEdge(s,e, v));
}
int useEdge = 0;
int result = 0;
while(useEdge < N - 1) {
pEdge now = que.poll();
if(find(now.s) != find(now.e)) { // 같은 부모가 아니라면 연결해도 사이클이 생기지 않음
union(now.s, now.e);
result = result + now.v;
useEdge++;
}
}
Union 연산 : 대표 노드끼리 연결하기
a = find(a);
b = find(b);
if(a != b) {
parent[b] = a;
}
Find 연산
if(a == parent[a]) {
return a;
}
else {
return parent[a] = find(parent[a]); // 경로압축
}
class pEdge implements Comparable<pEdge> {
int s;
int e;
int v;
pEdge(int s, int e, int v) {
this.s = s;
this.e = e;
this.v = v;
}
@Override
public int compareTo(pEdge o) {
// 가중치를 기준으로 오름차순 정렬을 하기 위해 compareTo 재정의하기
return this.v - o.v;
}
}
에지 리스트에 에지 정보를 저장한 후 부모 노드를 초기화한다. 사이클 생성 유무를 판단하기 위한 파인드용 부모 노드도 초기화한다. 크루스칼 알고리즘을 수행한다. 현재 미사용 에지 중 가중치가 가장 작은 에지를 선택하고, 이 에지를 연결했을 때 사이클의 발생 유무를 판단한다. 사이클이 발생하면 생략하고, 발생하지 않으면 에지 값을 더한다. 에지를 더한 횟수가 V(노드 개수) - 1 이 될 때까지 반복하고, 반복이 끝나면 에지의 가중치를 모두 더한 값을 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1197 {
static PriorityQueue<pEdge> que;
static int[] parent;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
parent = new int[n + 1];
que = new PriorityQueue<>();
for(int i = 0; i < n; i++) {
parent[i] = i;
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
que.add(new pEdge(a, b, c));
}
int useEdge = 0;
int result = 0;
while(useEdge < n - 1) {
pEdge now = que.poll();
if(find(now.a) != find(now.b)) { // 같은 부모가 아니라면 연결해도 사이클이 생기지 않음
union(now.a, now.b);
result = result + now.c;
useEdge++;
}
}
System.out.println(result);
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) {
parent[b] = a;
}
}
private static int find(int a) {
if(a == parent[a]) {
return a;
}
else {
return parent[a] = find(parent[a]);
}
}
}
class pEdge implements Comparable<pEdge>{
int a;
int b;
int c;
public pEdge(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
@Override
public int compareTo(pEdge o) {
return this.c - o.c;
}
}
66번 블우이웃 돕기
내가 떠올린 풀이 해설
인접 행렬의 형태로 데이터가 들어오기 때문에 이 부분을 최소 신장 트리가 가능한 형태로 변형하는 것이 이 문제의 핵심이다. 먼저 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장한다. 이때 i와 j가 같은 곳의 값은 같은 컴퓨터를 연결한다는 의미이므로 별도 에지로 저장하지 않고 나머지 위치의 값들을 i -> j로 가는 에지로 생성하고, 에지 리스트에 저장하면 최소 신장 트리로 변형할 수 있다.
입력 데이터의 정보를 배열에 저장한다. 먼저 입력으로 주어진 문자열을 숫자로 변환해 총합으로 저장한다. 소문자는 현재 문자 - 'a' + 1, 대문자는 현재 문자 - 'A' + 27 변환한다. i와 j가 다른 경우에는 다른 컴퓨터를 연결하는 랜선이므로 에지리스트에 저장한다. 저장된 에지 리스트를 바탕으로 최소 신장 트리 알고리즘을 수행한다. 최소 신장 트리의 결괏값이 다솜이가 최소한으로 필요한 렌선의 길이이므로 처음 저장해 둔 랜선의 총합에서 최소 신장 트리의 결괏값을 뺀 값을 정답으로 출력한다. 최소 신장 트리에서 사용한 에지 개수가 n - 1이 아닌 경우에는 모든 컴퓨터를 연결할 수 없다는 의미이므로 -1을 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1414 {
static int n, sum;
static PriorityQueue<lEdge> que;
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
que = new PriorityQueue<>();
for(int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
char[] tmpc = st.nextToken().toCharArray();
for(int j = 0; j < n; j++) {
int tmp = 0;
if(tmpc[j] >= 'a' && tmpc[j] <= 'z') {
tmp = tmpc[j] - 'a' + 1;
}
else if(tmpc[j] >= 'A' && tmpc[j] <= 'Z') {
tmp = tmpc[j] - 'A' + 27;
}
sum = sum + tmp;
if(i != j && tmp != 0) {
que.add(new lEdge(i, j, tmp));
}
}
}
parent = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
}
int useEdge = 0;
int result = 0;
while(!que.isEmpty()) {
lEdge now = que.poll();
if(find(now.s) != find(now.e)) {
union(now.s, now.e);
result = result + now.v;
useEdge++;
}
}
if(useEdge == n - 1) {
System.out.println(sum - result);
}
else {
System.out.println(-1);
}
}
private static void union(int s, int e) {
s = find(s);
e = find(e);
if(s != e) {
parent[e] = s;
}
}
private static int find(int s) {
if(s == parent[s]) {
return s;
}
else {
return parent[s] = find(parent[s]);
}
}
}
class lEdge implements Comparable<lEdge> {
int s;
int e;
int v;
public lEdge(int s, int e, int v) {
this.s = s;
this.e = e;
this.v = v;
}
@Override
public int compareTo(lEdge o) {
return this.v - o.v;
}
}
오늘의 회고
오늘은 최소 신장 트리 문제 2문제를 풀었습니다. 코드를 구현하는데 어려웠습니다. 반복해서 제가 직접 구현할 수 있게 만들겠습니다. 오늘 날씨가 너무 더운데 모든 취준생분들 화이팅입니다. 열심히 나아가겠습니다. 모두 화이팅입니다.
