066 : 불우 이웃 돕기

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 기부가능한 최대의 랜선 길이		I // 컴퓨터 갯수 N N x N 행렬에 w가 주어진 O // 기부가능 랜선 길이 최댓값

*i번째 줄의 j값이 0일 경우 > 연결랜선 x

*a > z : 1~26 // A > Z : 27 ~ 52

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    // point recognition
    static int[] label;
    static int N, sum;

    // box recognition
    static PriorityQueue<lEdge> queue;

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

        // Input Supply Cable
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // point and box
        N = Integer.parseInt(st.nextToken());
        queue = new PriorityQueue<>();
        
        // point supply
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            char[] tempc = st.nextToken().toCharArray();
            for (int j = 0; j < N; j++) {
                int temp = 0;
                if (tempc[j] >= 'a' && tempc[j] <= 'z')
                    temp = temp[j] - 'a' + 1;
                else if (tempc[j] >= 'A' && tempc[j] <= 'Z')
                    temp = tempc[j] - 'A' + 27;
                sum = sum + temp;
                if (i != j && temp != 0)
                    queue.add(new lEdge(i, j, temp));
            }
        }
        
        // Operating Minimun-spanning TRee
        label = new int[N];
        for (int i = 0; i < label.length; i++) {
            label[i] = i;
        }
        int usedEdge = 0;
        int plate = 0;
        while (!queue.isEmpty()) {
            lEdge now = queue.poll();
            if (find(now.s) != find(now.e)) {
                union(now.s, now.e);
                plate = plate + now.v;
                usedEdge++;
            }
        }

        // Output Extracting Cable
        if (usedEdge == N-1)
            System.out.println(sum-plate);
        else
            System.out.println(-1);

    }

    // External Module : union
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b)
            label[b] = a;
    }

    // External Module : find
    public static int find(int a) {
        if (a == label[a])
            return a;
        else
            return label[a] = find(label[a]);
    }
}

// External Class : lEdge
class lEdge implements Comparable<lEdge> {
    int s;
    int e;
    int v;
    lEdge (int s, int e, int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
    @Override
    public int compareTo(lEdge o) {
        return this.v - o.v;
    }
}