오늘 풀어본 문제는
백준 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);
    }
}

📝 풀이

MST(Minimum Spanning Tree)문제입니다.
크루스칼 알고리즘을 적용하여 풀이했습니다. 크루스칼 알고리즘은 가중치가 적은 순서대로 정렬한 후 사이클 생성여부를 확인하여 트리를 확장해 나가는 방식입니다.
먼저 간선의 정보를 담은 ArrayList를 가중치 값을 기준으로 정렬해주고, 가장 작은값부터 탐색을 시작합니다. 만약 선택된 가중치를 가진 각 정점들의 부모가 같다면, 사이클이 생성되므로 넘어가주고, 부모가 다를때만 union 함수를 호출하여 결과에 포함해줍니다.
모든 정점을 포함하려면 v-1까지만 진행하면 되므로, 카운트를 활용하여 v-1에 도달하면 탐색을 종료한 후 answer을 출력해줍니다.

📜 후기

이전에 비슷한 문제를 풀었을 때 프림 알고리즘을 적용했었기 때문에, 이번엔 크루스칼 알고리즘으로 문제를 풀이해 보았습니다. 두 알고리즘의 정확한 차이를 몰랐었는데, 이번에 둘다 풀이해보니, 프림 알고리즘은 정점 기준, 크루스칼은 간선 기준으로 탐색이 진행되므로 주어진 조건에 따라 선택하여 풀이하면 될 것 같습니다.