[BOJ][Java] 1414번 불우이웃돕기

문제 설명

문제 링크 : https://www.acmicpc.net/problem/1414

 

문제를 살펴보면 해결하는 방법은 최소신장 트리를 이용하면 간단히 해결할 수 있다.

주의해야 하는 것은 문자를 정수로 변경하는 것과

A -> A로 돌아오는 간선은 제외하고 생각해야 한다는 것이다.

 

예제 입력 1번을 그래프로 표현하면 위와 같다.

 

문제를 해결하는 과정은 아래와 같다.

1. 주어진 간선(랜선)의 총합을 구한다 (sum)

2. 자기 자신에게 돌아오는 간선(랜선)을 제외하고 나머지 간선을 가중치를 기준 오름차순으로 정렬한다.

3. MST알고리즘을 통해 모든 정점을 잇는 거리의 최단거리를 구한다(minSum)

4. 만약 고른 간선의 길이가 주어진 정점의 개수 - 1 개가 아니라면 -1을 출력하고, 맞다면 sum - minSum 값을 출력한다.

 

package boj;

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

public class BOJ1414 {
    static int[] heads;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Edge> edges = new ArrayList<>();
        int sum = 0;

        heads = new int[N];
        for(int i = 0; i < heads.length; i++){
            heads[i] = i;
        }

        for(int i = 0; i < N; i++){
            char[] temp = br.readLine().toCharArray();
            for(int j = 0; j < N; j++){
                int num = change(temp[j] + 0);
                if(i == j){
                    sum += num;
                }else if(num != 0){
                    sum += num;
                    edges.add(new Edge(i,j,num));
                }
            }
        }

        edges.sort((o1,o2) -> o1.cost - o2.cost);
        int count = 0;
        int minSum = 0;

        for(int i = 0; i < edges.size(); i++){
            Edge now = edges.get(i);

            if(find(now.node1) != find(now.node2)){
                union(now.node1, now.node2);
                count++;
                minSum += now.cost;
            }
        }

        if(count != N - 1) System.out.println(-1);
        else System.out.println(sum - minSum);

        // 0 = 48
        // A = 65
        // Z = 90
        // a = 97
        // z = 122

    }
    static int find(int num){
        if(num == heads[num]) return num;
        return heads[num] = find(heads[num]);
    }

    static void union(int a, int b){
        int aHead = find(a);
        int bHead = find(b);

        if(aHead != bHead) heads[bHead] = aHead;
    }

    static int change(int num){
        if(num == 48) return 0;
        else if (num >= 65 && num <= 90) return num - 38;
        else return num - 96;
    }

    static class Edge{
        int node1;
        int node2;
        int cost;

        public Edge(int node1, int node2, int cost){
            this.node1 = node1;
            this.node2 = node2;
            this.cost = cost;

        }
    }
}