문제

문제 바로가기

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static int n; // 컴퓨터의 수
    static int m; // 연결할 수 있는 선의 수
    static int[][] network; // 각 컴퓨터가 연결된 정보들
    static StringTokenizer st;
    static int costs;
    static int[] arr; // 어디에 연결되어 있는지 확인하기 위한

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = i;
        }

        network = new int[m][3];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            network[i][0] = Integer.parseInt(st.nextToken());
            network[i][1] = Integer.parseInt(st.nextToken());
            network[i][2] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(network, Comparator.comparing(o -> o[2])); // 비용을 기준으로 오름차순 정렬

//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < 3; j ++) {
//                System.out.print(network[i][j]);
//            }
//            System.out.println();
//        }

        for (int[] net : network) {
            if (union(net[0], net[1])) {
                costs += net[2];
            }
            System.out.println(Arrays.toString(arr));
        }
        System.out.println(costs);
    }

    static int find(int x) { // 연결되었다면 끝지점이 어디인지 탐색
        if (arr[x] == x) {
            return x;
        }
        return find(arr[x]);
    }

    static boolean union(int start, int end) {
        int s = find(start);
        int e = find(end);

        if (s != e) {
            arr[e] = s;
            return true;
        }
        return false;
    }
}

위 문제는 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구하는 것이다. 처음 크루스칼 알고리즘 문제를 풀어보았기에 유튜브에서 강의를 들어보니 비용이 제일 낮은 순부터 연결을 하되 순환이 생기지 않도록 연결을 하는 것이 중요하다!

먼저 입력값을 전체로 받고 이때 연결되는 두 좌표와 비용을 한꺼번에 넣기 위해서 2차원 배열을 선언할 때 연결 갯수만큼 행을 만들고 열은 3개로 선언하였다. 그 후에 비용을 기준으로 오름차순 정렬을 하기 위해 Comparator을 이용했다.

그 후, 여기서 같이 나오는 개념이 Union find인데 좌표를 연결하기전에 먼저 find를 통해 각 좌표가 어디까지 최종적으로 연결되어 있는지? 그것을 약간 추적한다는 개념으로 이해했다!! 이때 find를 해서 나온 좌표값이 서로 다르다면 순환 사이클이 생기지 않다는 의미이기 때문에 각 좌표를 연결해준다.

이렇게 union이 가능해지면 전체 비용에다가 비용을 추가해주면서 최종적으로 비용을 출력하면 된다.