[백준/Graph] 1922번 네트워크 연결 (JAVA)

문제

---

풀이

며칠 전에 정리했던 Kruskal & Union-Find 알고리즘을 적용할 수 있는 문제였다. 근데 문제를 보고 바로 이 알고리즘을 떠올리지 못하고 조금 고민을 한 후에 생각이 나서 나 자신에게 또 살짝쿵 실망을 했다!

그래도 아이디어를 떠올린 후에는 많이 오래 걸리지 않고 알고리즘을 구현할 수 있었다. 한 가지 실수를 했었는데, Union-Find 알고리즘의 union() 메서드에서, parentNodes를 업데이트 할 때 인덱스를 잘못 부여하는 바람에 알고리즘이 제대로 작동하지 않았다. 최상위 부모 노드의 부모를 부여하는 거니까 parentX가 올바른 인덱스값이 된다.

아무튼 이번 문제로 머리에 다시 한 번 두 알고리즘을 머리에 새길 수 있었다. 굿굿

코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

    private static final int SRC = 0;
    private static final int DST = 1;
    private static final int WEIGHT = 2;

    private static BufferedReader br;
    private static BufferedWriter bw;

    private static int nodeCount;
    private static int edgeCount;
    private static int[][] costs;

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        initParams();
        int costForConnection = calcCostForConnection();
        bw.append(Integer.toString(costForConnection));

        br.close();
        bw.close();
    }

    private static void initParams() throws IOException {
        nodeCount = Integer.parseInt(br.readLine());
        edgeCount = Integer.parseInt(br.readLine());
        costs = new int[edgeCount][3];
        for (int i = 0; i < edgeCount; i++) {
            String[] line = br.readLine().split(" ");
            costs[i][SRC] = Integer.parseInt(line[SRC]) - 1;
            costs[i][DST] = Integer.parseInt(line[DST]) - 1;
            costs[i][WEIGHT] = Integer.parseInt(line[WEIGHT]);
        }
    }

    private static int calcCostForConnection() {
        Arrays.sort(costs, (Comparator.comparingInt(o -> o[WEIGHT])));
        int[] parentNodes = createCycleTable();
        int answer = 0;
        for (int[] edge : costs) {
            if (!hasSameParent(parentNodes, edge[SRC], edge[DST])) {
                union(parentNodes, edge[SRC], edge[DST]);
                answer += edge[WEIGHT];
            }
            if (pathCreated(parentNodes)) break;
        }
        return answer;
    }

    private static int[] createCycleTable() {
        int[] result = new int[nodeCount];
        for (int i = 0; i < nodeCount; i++) result[i] = i;
        return result;
    }

    private static boolean hasSameParent(int[] parentNodes, int a, int b) {
        return findParent(parentNodes, a) == findParent(parentNodes, b);
    }

    private static int findParent(int[] parentNodes, int node) {
        if (parentNodes[node] == node) return node;
        return findParent(parentNodes, parentNodes[node]);
    }

    private static void union(int[] parentNodes, int a, int b) {
        int parentA = findParent(parentNodes, a);
        int parentB = findParent(parentNodes, b);
        if (parentA > parentB) parentNodes[parentA] = parentB;
        else parentNodes[parentB] = parentA;
    }

    private static boolean pathCreated(int[] parentNodes) {
        for (int i = 0; i < parentNodes.length - 1; i++)
            if (parentNodes[i] != parentNodes[i + 1]) return false;
        return true;
    }
}