백준 1197 최소 스패닝 트리 (Java,자바)
오늘 풀어본 문제는
백준 1197번 최소 스패닝 트리 입니다.
📕 문제 링크
❗️코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Node
{
int start, end, weight;
public Node(int start, int end, int weight)
{
this.start = start;
this.end = end;
this.weight = weight;
}
}
public class Main {
static ArrayList<Node> al;
static int [] parents;
static int v;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
al = new ArrayList<>();
parents = new int[v+1];
for(int i = 1; i <= v; ++i) parents[i] = i;
for(int i = 0; i < e; ++i)
{
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
al.add(new Node(a,b,c));
}
al.sort(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.weight - o2.weight;
}
});
int cnt = 0;
for(Node cur : al)
{
if(cnt == v-1) break;
if(!(getParent(cur.start) == getParent(cur.end)))
{
union(cur.start,cur.end);
cnt++;
answer += cur.weight;
}
}
System.out.print(answer);
}
static int getParent(int child)
{
if(parents[child] == child) return child;
else
{
return parents[child] = getParent(parents[child]);
}
}
static void union(int p, int c)
{
parents[getParent(c)] = getParent(p);
}
}
📝 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Node
{
int start, end, weight;
public Node(int start, int end, int weight)
{
this.start = start;
this.end = end;
this.weight = weight;
}
}
public class Main {
static ArrayList<Node> al;
static int [] parents;
static int v;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
al = new ArrayList<>();
parents = new int[v+1];
for(int i = 1; i <= v; ++i) parents[i] = i;
for(int i = 0; i < e; ++i)
{
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
al.add(new Node(a,b,c));
}
al.sort(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.weight - o2.weight;
}
});
int cnt = 0;
for(Node cur : al)
{
if(cnt == v-1) break;
if(!(getParent(cur.start) == getParent(cur.end)))
{
union(cur.start,cur.end);
cnt++;
answer += cur.weight;
}
}
System.out.print(answer);
}
static int getParent(int child)
{
if(parents[child] == child) return child;
else
{
return parents[child] = getParent(parents[child]);
}
}
static void union(int p, int c)
{
parents[getParent(c)] = getParent(p);
}
}
📝 풀이
MST(Minimum Spanning Tree)문제입니다.
크루스칼 알고리즘을 적용하여 풀이했습니다. 크루스칼 알고리즘은 가중치가 적은 순서대로 정렬한 후 사이클 생성여부를 확인하여 트리를 확장해 나가는 방식입니다.
먼저 간선의 정보를 담은 ArrayList를 가중치 값을 기준으로 정렬해주고, 가장 작은값부터 탐색을 시작합니다. 만약 선택된 가중치를 가진 각 정점들의 부모가 같다면, 사이클이 생성되므로 넘어가주고, 부모가 다를때만 union 함수를 호출하여 결과에 포함해줍니다.
모든 정점을 포함하려면 v-1까지만 진행하면 되므로, 카운트를 활용하여 v-1에 도달하면 탐색을 종료한 후 answer을 출력해줍니다.
📜 후기
이전에 비슷한 문제를 풀었을 때 프림 알고리즘을 적용했었기 때문에, 이번엔 크루스칼 알고리즘으로 문제를 풀이해 보았습니다. 두 알고리즘의 정확한 차이를 몰랐었는데, 이번에 둘다 풀이해보니, 프림 알고리즘은 정점 기준, 크루스칼은 간선 기준으로 탐색이 진행되므로 주어진 조건에 따라 선택하여 풀이하면 될 것 같습니다.
Author And Source
이 문제에 관하여(백준 1197 최소 스패닝 트리 (Java,자바)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jh5253/백준-1197-최소-스패닝-트리-Java자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)