[JAVA] 백준 1414 스패닝 트리

 

 

 

1414번: 불우이웃돕기

문제

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

풀이

다솜이가 기부할 수 있는 랜선의 길이는 자신의 N개의 컴퓨터를 랜선으로 연결하고 남는 랜선을 기부할 수 있다.

이때, 최대로 기부할 수 있는 랜선의 길이는 자신의 N개의 컴퓨터를 최단 거리의 랜선으로 연결하고 연결하지 않는 남은 랜선을 기부할 수 있다.

따라서 랜선들로 스패닝 트리를 구성하고 스패닝 트리를 구성하고 있지 않은 랜선들의 길이의 합을 구하면 된다.

📌 입력

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine())+1;
        PriorityQueue<Edge> q = new PriorityQueue<>((o1, o2) -> o1.weight-o2.weight);

        A = new int[N];
        for(int i=1; i<N; i++){
            A[i] = i;
        }
        for(int i=1; i<N; i++){
            char[] d = br.readLine().toCharArray();
            for(int j=0;j<d.length; j++){
                if(d[j] != '0') {
                    q.offer(new Edge(i, j + 1, wireLength(d[j])));
                }
            }
        }

    static int wireLength(char a){
        if(a >= 'a' && a <= 'z'){
            return a - 'a' + 1;
        }else if(a >= 'A' && a <= 'Z'){
            return a - 'A' + 27;
        }
        return 0;
    }

PriorityQueue : 간선 즉, 랜선들을 최소 길이부터 정렬하기 위해서 사용했다.

입력으로 받은 알파벳을 길이로 변경하기 위해서 wireLength 메서드를 만들어서 사용했다.

📌 스패닝 트리 구성

        int answer = 0;
        int flag = 0;
        while (!q.isEmpty()){
            Edge e = q.poll();
            if(find(e.start) != find(e.destination)){
                union(e.start, e.destination);
                flag++;
            }else{
                answer += e.weight;
            }
        }

기부할 수 있는 최대 길이의 랜선을 출력하기 위해서 answer를 선언하였고, 모든 컴퓨터를 랜선으로 연결할 수 없는 경우 -1을 출력하여야 하기 때문에 flag를 두어서 스패닝 트리가 구성된 간선의 개수를 카운트하였다.

1. 만약 간선(랜선)의 출발지와 목적지가 유니온 파인드 집합에서 같은 집합에 속하지 않는다면, 두 정점을 같은 집합에 포함시켜 스패닝 트리를 구성한다.
2. 만약 같은 유니온 파인드 집합에 속한다면, 1 → 1로 즉, 자기 자신으로 가는 랜선이거나 스패닝 트리의 사이클이 생길 수 있기 때문에 스패닝 트리를 구성할 수 없기 때문에 랜선의 길이를 합해준다.

📌 출력

        System.out.println(flag == N-2 ? answer : -1);

스패닝 트리를 구성하는 간선(랜선)의 수가 N-2 (위의 입력에서 N+1을 하였다.)이라면 스패닝 트리를 구성하는 간선의 수를 만족하므로, 정답을 출력해준다.

만약 N-2가 아니라면 스패닝 트리를 구성하지 못한 것이므로, -1을 출력한다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine())+1;
        PriorityQueue<Edge> q = new PriorityQueue<>((o1, o2) -> o1.weight-o2.weight);

        A = new int[N];
        for(int i=1; i<N; i++){
            A[i] = i;
        }
        for(int i=1; i<N; i++){
            char[] d = br.readLine().toCharArray();
            for(int j=0;j<d.length; j++){
                if(d[j] != '0') {
                    q.offer(new Edge(i, j + 1, wireLength(d[j])));
                }
            }
        }

        int answer = 0;
        int flag = 0;
        while (!q.isEmpty()){
            Edge e = q.poll();
            if(find(e.start) != find(e.destination)){
                union(e.start, e.destination);
                flag++;
            }else{
                answer += e.weight;
            }
        }

        System.out.println(flag == N-2 ? answer : -1);

    }
    static class Edge{
        int start;
        int destination;
        int weight;
        public Edge(int start, int destination, int weight){
            this.start = start;
            this.destination = destination;
            this.weight = weight;
        }
    }

    static void union(int a, int b){
        A[find(a)] = find(b);
    }
    static int find(int a){
        if(A[a] == a) return a;
        else return A[a] = find(A[a]);
    }

    static int wireLength(char a){
        if(a >= 'a' && a <= 'z'){
            return a - 'a' + 1;
        }else if(a >= 'A' && a <= 'Z'){
            return a - 'A' + 27;
        }
        return 0;
    }

}

결과