[백준] 1774번. 우주신과의 교감(JAVA)

문제

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

---

풀이(25분)

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

public class Main {

    // 이미 교감하는 존재가 있다!
    // 우주신들과 교감의 통로가 길어지면 힘듬
    // 거리는 2차원 좌표계상의 거리와 같다
    // 새로 만들어야 할 정신적인 통로의 길이들의 합이 최소가 되게
    // 그럼 일단 연결된 애들은 부모를 같게 한다.
    // 나머지 모든 점들에 대해 거리를 구하고, 노드에 넣자!
    static int n;
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static int[] parent;
    static int answer;
    static long sum = 0;

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

        n = Integer.parseInt(br.readLine());
        parent = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            String s = br.readLine();
            for (int j = 0; j < n; j++) {
                int length = alphabetToInteger(s.charAt(j));
                if (length == 0) continue;

                sum += length;
                pq.add(new Node(i, j, length));
            }
        }

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int startParent = find(cur.start);
            int endParent = find(cur.end);

            if (startParent != endParent) {
                union(startParent, endParent);
                answer += cur.length;
            }
        }

        // 모든 노드가 연결되어 있는지 확인
        int firstParent = find(0);
        for (int i = 1; i < n; i++) {
            if (find(i) != firstParent) {
                System.out.println(-1);
                return;
            }
        }

        System.out.println(sum - answer);
    }

    static void union(int a, int b) {
        parent[b] = a;
    }

    // 부모를 찾는 메서드
    static int find(int idx) {
        if (parent[idx] != idx) {
            parent[idx] = find(parent[idx]); // 경로 압축
        }
        return parent[idx];
    }

    // 입력으로 들어온 알파벳을 int형으로 전환해주는 메서드
    static int alphabetToInteger(char alphabet) {
        if (alphabet == '0') return 0;
        if (alphabet >= 'A' && alphabet <= 'Z') {
            return alphabet - 'A' + 27;
        }
        return alphabet - 'a' + 1;
    }

    static class Node implements Comparable<Node> {
        int start, end, length;

        public Node(int start, int end, int length) {
            this.start = start;
            this.end = end;
            this.length = length;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.length, o.length);
        }
    }
}

---

문제 풀이 전략

 

최소 신장 트리를 안다면 어려운 문제는 아니었다. 

 

입력을 받으면 알파벳 -> 해당하는 숫자로 전환하여 배열에 저장한다.

간선의 길이가 0이 아니라면 우선순위 큐에 추가하여 모든 간선의 탐색을 진행한다.

 

최종적으로 모든 노드가 연결되어 있다면 전체 노드의 길이에서 연결시킨 경로만큼을 빼준다.