[Do It! 코딩테스트 자바편(김종관)] 문제 066(백준 1414번)

느낀점

• 인접 행렬로 주어지는 정보를 에지 리스트로 저장하는 아이디어는 교재에서 얻었다.
• 그 후 구현은 쉬었지만, 주어지는 정보를 변형해서 알맞은 자료구조로 저장하는 아이디어는 책의 도움을 받아서 더 정진해야 겠다고 생각했다.

문제

불우이웃돕기(백준: 1414번)

풀이

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

public class Main {
    static int computerCnt, sumLength = 0;
    static PriorityQueue<Edge> edgeList = new PriorityQueue<>();
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        computerCnt = Integer.parseInt(br.readLine());
        parent = new int[computerCnt];
        for (int i = 0; i < computerCnt; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < computerCnt; i++) {
            char[] tmpArr = br.readLine().toCharArray();
            for (int j = 0; j < computerCnt; j++) {
                int tmp = 0;
                if (tmpArr[j] >= 'a' && tmpArr[j] <= 'z')
                    tmp = tmpArr[j] - 'a' + 1;
                else if (tmpArr[j] >= 'A' && tmpArr[j] <= 'Z')
                    tmp = tmpArr[j] - 'A' + 27;
                sumLength += tmp;

                if (i != j && tmp != 0)
                    edgeList.add(new Edge(i, j, tmp));
            }
        }

        int useEdgeCnt = 0;
        int MSTResult = 0;
        while (!edgeList.isEmpty()) {
            Edge now = edgeList.poll();
            int s = now.s;
            int e = now.e;
            int v = now.v;
            if (find(s) != find(e)) {
                union(s, e);
                useEdgeCnt++;
                MSTResult += v;
            }
        }

        if (useEdgeCnt == computerCnt - 1)
            System.out.println(sumLength - MSTResult);
        else
            System.out.println(-1);
    }

    private static void union(int s, int e) {
        int root_s = find(s);
        int root_e = find(e);
        if (root_s != root_e)
            parent[root_s] = root_e;
    }

    private static int find(int index) {
        if (index == parent[index])
            return index;
        else
            return parent[index] = find(parent[index]);
    }

}

class Edge implements Comparable<Edge> {
    int s;
    int e;
    int v;

    public Edge(int s, int e, int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }

    @Override
    public int compareTo(Edge e) {
        return this.v - e.v;
    }

}