문제

BOJ 1197: 최소 스패닝 트리 https://www.acmicpc.net/problem/1197

풀이

조건

• 최소 스패닝 트리를 구한다.

풀이 순서

• 크루스칼 알고리즘을 사용한다.
• 간선의 비용을 오름차순으로 정렬한다.
• Union&Find를 사용해 트리에 사이클이 있는지 확인한다.

코드

Java

import java.util.*;
import java.io.*;

public class Main {

    // 집합 기록할 배열
    static int[] parent;
    static int V, E;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine(), " ");
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        List<Edge> edges = new ArrayList<>();
        int answer = 0;

        for(int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            edges.add(new Edge(s, e, cost));
        }

        // 비용을 오름차순으로 정렬
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return Integer.compare(o1.cost, o2.cost);
            }
        });

        // 집합 기록할 배열 초기화
        parent = new int[V + 1];
        for(int i = 1; i <= V; i++) {
            parent[i] = i;
        }

        for(int i = 0; i < E; i++) {
            Edge edge = edges.get(i);

            // 같은 집합이 아니면
            if(!isSameParent(edge.s, edge.e)) {
                // 집합 합치기
                union(edge.s, edge.e);
                // 비용 누적
                answer += edge.cost;
            }
        }

        System.out.println(answer);
    }

    // 어느 집합인지 찾기
    // parent 배열의 값으로 찾음
    static int find(int x) {
        if(parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    // 같은 집합인지 확인하기
    static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);

        if(x == y) {
            return true;
        }
        return false;
    }

    // 합치기
    // 더 작은 숫자가 집합 이름이 됨
    // (x < y)
    static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if(x != y) {
            parent[y] = x;
        }
    }

    static class Edge {
        int s, e, cost;

        public Edge(int s, int e, int cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }
    }

}

정리

• 우테캠 1차 코딩테스트 마지막 문제에 나온 유형인데 제대로 풀지 못해 연습해봤다.
• MST를 크루스칼 알고리즘으로 구하는 기초 문제였다.