백준 6497 전력난 (Java)

https://www.acmicpc.net/problem/6497

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

class Pair implements Comparable<Pair>{
    int z;
    int x, y;

    public Pair(int z, int x, int y) {
        this.z = z;
        this.x = x;
        this.y = y;
    }


    @Override
    public int compareTo(Pair o) {
        return z - o.z;
    }
}


public class Main {

    static int[] parent;
    static List<Pair> list;

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


        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer tokenizer;

        while (true) {

            tokenizer = new StringTokenizer(reader.readLine());

            int m = Integer.parseInt(tokenizer.nextToken());
            int n = Integer.parseInt(tokenizer.nextToken());

            if (m == 0 && n == 0) {
                break;
            }



            int mCost = 0;      //최소 비용
            int tCost = 0;      //전체 비용

            list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                tokenizer = new StringTokenizer(reader.readLine());

                int x = Integer.parseInt(tokenizer.nextToken());
                int y = Integer.parseInt(tokenizer.nextToken());
                int z = Integer.parseInt(tokenizer.nextToken());

                list.add(new Pair(z, x, y));
                tCost += z;
            }

            Collections.sort(list);

            parent = new int[m];

            for (int i = 0; i < m; i++) {
                parent[i] = i;
            }


            for (Pair cur : list) {

                if (findParent(cur.x) != findParent(cur.y)) {
                    uni(cur.x, cur.y);
                    mCost += cur.z;
                }
            }

            System.out.println(tCost - mCost);
        }


        writer.flush();
        writer.close();
        reader.close();

    }

    static int findParent(int k) {
        if (parent[k] == k) {
            return k;
        }
        return parent[k] = findParent(parent[k]);
    }

    static void uni(int a, int b) {
        int parentA = findParent(a);
        int parentB = findParent(b);

        if(parentA<parentB){
            parent[parentB] = parentA;
        }else{
            parent[parentA] = parentB;
        }
    }
}

 

1. 문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

2. 풀이

이 문제는 여러 개의 테스트 케이스가 주어지고, m, n이 모두 0일 경우 프로그램을 종료한다.

        while(true){
            
            tokenizer = new StringTokenizer(reader.readLine());

            int m = Integer.parseInt(tokenizer.nextToken());
            int n = Integer.parseInt(tokenizer.nextToken());

            if (m == 0 && n == 0) {
                break;
            }
            
            ...

이에 따라 이를 입력받고, 둘다 0이면 무한루프를 빠져나가고 프로그램을 종료한다.

 

 모든 집 사이를 이동할 수 있고, 길의 미터 수만큼 돈이 들어가며, 이를 최소로 구하는 문제이다. 즉 MST 문제로 크루스칼 알고리즘을 사용하여 해결할 수 있다.

class Pair implements Comparable<Pair>{
    int z;
    int x, y;

    public Pair(int z, int x, int y) {
        this.z = z;
        this.x = x;
        this.y = y;
    }


    @Override
    public int compareTo(Pair o) {
        return z - o.z;
    }
}

Main(){

            ...

            int mCost = 0;      //최소 비용
            int tCost = 0;      //전체 비용

            list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                tokenizer = new StringTokenizer(reader.readLine());

                int x = Integer.parseInt(tokenizer.nextToken());
                int y = Integer.parseInt(tokenizer.nextToken());
                int z = Integer.parseInt(tokenizer.nextToken());

                list.add(new Pair(z, x, y));
                tCost += z;
            }

            Collections.sort(list);

절약 비용을 구해야 하므로 현재 거리의 모든 비용을 계산하여 저장하고, 크루스칼 알고리즘을 사용하기 위해 비용의 오름차순으로 리스트를 정렬한다.

            parent = new int[m];

            for (int i = 0; i < m; i++) {
                parent[i] = i;
            }


            for (Pair cur : list) {

                if (findParent(cur.x) != findParent(cur.y)) {
                    uni(cur.x, cur.y);
                    mCost += cur.z;
                }
            }

            System.out.println(tCost - mCost);

 이제 처음부터 가로등을 켤 길을 만들어보자. parent를 초기화하고, 두 노드의 부모가 같지 않으면 이를 연결, 최소 비용을 추가해준다. 연산이 끝나고 전체 비용에서 최소 비용을 빼어 절약 비용을 출력해준다. 아래 코드는 union-find 관련 함수이다.

    static int findParent(int k) {
        if (parent[k] == k) {
            return k;
        }
        return parent[k] = findParent(parent[k]);
    }

    static void uni(int a, int b) {
        int parentA = findParent(a);
        int parentB = findParent(b);

        if(parentA<parentB){
            parent[parentB] = parentA;
        }else{
            parent[parentA] = parentB;
        }
    }