크루스칼 알고리즘을 통해서 모든 집을 방문하는 최단 경로를 구하였을 때, 유지비가 가장 높은 길을 제거하면
2개의 마을로 분리되며 최소 유지비의 합을 구할 수 있습니다.
예제입력 진행과정을 보시는 것이 이해하기 쉬울 것입니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 7
M : 12
X : 2
2. 크루스칼 알고리즘을 이용하여 모든 집을 연결하는 최단 거리를 만듭니다.
사전 작업
1. 크루스칼 알고리즘을 사용하기 위해서 모든 길을 유지비 기준 오름차순 정렬!
2. Union-Find를 사용하기 위해서 parent[] 배열 모두 자기 번호로 초기화!
1
2
3
4
5
6
7
1
2
3
4
5
6
7
크루스칼 알고리즘 탐색 진행!
가장 유지비 낮은 길부터 탐색 후 Union-Find를 진행~
1
2
3
4
5
6
7
1
2
2
4
5
6
7
1
2
3
4
5
6
7
1
2
2
4
5
4
7
1
2
3
4
5
6
7
1
1
1
4
5
4
7
1
2
3
4
5
6
7
1
1
1
4
1
4
7
1
2
3
4
5
6
7
1
1
1
1
1
1
7
1
2
3
4
5
6
7
1
1
1
1
1
1
1
모든 도로 탐색 완료! 최단 경로 완성!
3. 남은 길 중 최대 유지비용의 길을 제거한 유지비의 합을 결과로 출력합니다.
가장큰 길 : 7 - 6의 길을 제거했을 때 아래와 같이 2개의 마을로 구분됩니다.
마을 1 : { 1, 2, 3, 4, 5, 6 }
마을 2 : { 7 }
남은 길 : 2 - 3, 4 -6 , 1 - 3, 2 - 5, 1 - 6
1 + 1 + 2 + 2 + 2 = 8
8결과로 출력합니다.
BufferedReader를 사용하여 입력되는 정보를 저장합니다.
StringTokenizer를 이용하여 길의 정보를 띄어쓰기 기준 나누었습니다.
Union-Find에 사용할 parent[]를 초기화하였습니다.
길을 유지비 기준 오름차순 정렬하였습니다.
크루스칼 알고리즘을 이용하여 최단 경로를 구합니다.
최단 경로에서 최대 유지비의 길을 제거한 유지비의 합을 결과로BufferedWriter에 저장하였습니다.
BufferedWriter에 저장된 결과값을 출력하였습니다.
union함수는 Union-Find에서 parent[]를 비교하여 변경해주는 역활을 합니다.
find함수 Union-Find에서 parent[]의 값을 찾는 역활을 합니다.
결과코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
//길 정보 저장 클래스
static class Node implements Comparable<Node>{
int A_idx, B_idx, value;
//A_idx, b_idx : 연결된 집 정보, value : 유지비
public Node(int A_idx, int B_idx, int value) {
this.A_idx = A_idx;
this.B_idx = B_idx;
this.value = value;
}
//유지비 기준 오름차순
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}
static int[] parent; //Union-Find에 사용할 배열
static StringBuilder answer = new StringBuilder();
static ArrayList<Node> road = new ArrayList<>(); //길 정보 저장 리스트
public static void main(String[] args) throws IOException{
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
parent = new int[N+1];
//사전 작업!
//parint[] 배열 각 집으로 초기화
for(int i=1;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());
road.add(new Node(A,B,C));
}
//사전 작업
//유지비 기준 길 오름차순 정렬
Collections.sort(road);
int sum = 0; //최단 경로에 유지비 합
int max = -1; //최단 경로에 최소 유지비 길
//크루스칼 알고리즘으로 탐색!
for(Node n : road) {
//연결 가능한지.
if(find(n.A_idx) != find(n.B_idx)) {
union(n.A_idx, n.B_idx); //Union-Find : Union 합치기!
sum += n.value; //유지비 더하기
max = Math.max(max, n.value); //유지비 최대값이지 확인
}
}
sum -= max; //마을을 2개로 분리하기 위해서 최대 길 제거!
bw.write(String.valueOf(sum)); //최소 유지비 BufferedWriter 저장
bw.flush();
bw.close();
br.close();
}
//Union-Find : Find 담당 함수
static int find(int a) {
if(parent[a] == a)
return a;
return parent[a] = find(parent[a]);
}
//Union-Find : Union 담당 함수
static void union(int a, int b) {
int pa = find(a);
int pb = find(b);
//parent[] 작은 값 기준으로 저장되도록 설정!
if(pa <= pb)
parent[pb] = parent[pa];
else
parent[pa] = parent[pb];
}
}
댓글