문제
동물원에서 막 탈출한 우너숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다.
마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.
풀이
문제를 대충 읽어봐도 그래프끼리 연결이 되고 모두가 연결이 되어야 하는데 분리시킨다는 말이 좀 걸렸었다.
근데 마지막에 최소라는 말을 듣고 크루스칼 알고리즘으로 신장트리를 만든 후 가장 큰 가중치 값으로 자를려고 했는데 여기서 실수가 가장 큰 가중치 값은 싸이클이 되었을 수도 있던 부분이라 유니온 시키는 가중치들 중에 가장 큰 값을 뺴줘야 하는 것이었다.
크루스칼 알고리즘을 간단하게 다시 보면
- 최소 신장 트리를 찾는 알고맂므
- Greedy를 이용하여 가중치 그래프의 모든 정점을 최소 비용을 연결하는 방법을 찾는 것
- 최소 신장트리: 가중치 그래프에서 간선으 가중치 값의 합이 최소가 되고 , 회로가 없이 모든 정점이 연결되어 있는 트리를 뽑아내는 것
- 신장 트리 : 그래프의 모든 정점이 연결되어 있고, 회로가 없는 그래프
동작과정
- 그래프의 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
- 오름차순으로 정렬된 리스트에서 간선들을 순서대로 하나씩 뽑는다.(낮은 가중치부터)
- 뽑은 간선이 싸이클을 이루지 않는다면 유니온시킨다
출
https://developer-hm.tistory.com/117
문제에서 코드로 보면
주어진 3가지 값을 Edge클래스를 통해받는다.
가중치를 기준으로 정렬한다. -> 오름차순
입력받은 그래프들을 모두 순회하며 싸이클을 이루는 형태인지 확인한다.
find메소드인데 첫 시작 parent배열은 자기 자신이 부모이고 union메소드를 통해 변경될 경우 end가 start에 부모가 된다.
union을 바뀌게[ 되버리면 해당 메소드에서 재귀를 통해 해당 값을 찾을 수 있다.
union 메소드를 통해 start와 end의 부모를 찾는다. 그러고 end 인덱스에 start값을 대입한다 여기서 start != end는
싸이클 검사다
마지막 답 부분인데 해당 부분에서 최소 신장트리로 연결된 간선 중 가장 큰 가중치를 최소신장트리를 만들 때 사용한 가중치에서 빼버린다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int parent[];
static ArrayList<Edge> graph = new ArrayList<Edge>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parent = new int[N+1];
int total =0;
for (int i = 1; i < N+1 ; i++) {
parent[i] = i;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost =Integer.parseInt(st.nextToken());
graph.add(new Edge(start,end,cost));
}
Collections.sort(graph,new Comparator<Edge>(){
@Override
public int compare(Edge o1, Edge o2){
return o1.cost - o2.cost;
}
});
int temp = 0;
for(Edge edge : graph){
if(find(edge.start) != find(edge.end)){
total += edge.cost;
union(edge.start,edge.end);
temp = edge.cost;
}
}
System.out.println(total - temp);
}
public static int find(int start){
if(parent[start] == start){
return start;
}
return parent[start] = find(parent[start]);
}
public static void union(int start,int end){
start = find(start);
end = find(end);
if(start != end){
parent[end] = start;
}
}
static class Edge{
int start;
int end;
int cost;
public Edge(int start,int end,int cost){
this.start = start;
this.end = end;
this.cost = cost;
}
}
}
'알고리즘' 카테고리의 다른 글
백준 No.18223 민준이와 마산 그리고 건우- JAVA (0) | 2023.03.13 |
---|---|
백준 No.6497 전력난 - JAVA (0) | 2023.03.12 |
백준 No.27112 시간 외 근무 멈춰! - JAVA (0) | 2023.03.10 |
백준 No.14284 간선 이어가기2 - JAVA (0) | 2023.03.06 |
백준 No.1783 병든 나이트 - JAVA (0) | 2023.03.06 |