우주신과의 교감(BJ_G3_1774)

1. 문제 링크

 

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

1774번: 우주신과의 교감

 

---

 

2. 나의 코드

메모리: 43928KB 
시간: 760ms 
코드 길이: 3556B
시간 복잡도 : O(N^2) >> 조합 생성 시
설명
- 각각의 노드를 입력 받은 후 조합 알고리즘을 사용하여 각 노드들의 거리를 계산해서 edgeList에 넣어주기
- 리스트 정렬
- 미리 연결된 코드는 union처리 해주기
- 크루스칼 알고리즘을 사용하여 최소 연결 거리 구하기

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_1774 {
    static List<Point> nodeList;
    static List<Edge> edgeList;
    static int V, P;    // 노드 갯수, 이미 열견된 통로 갯수
    static int[] parent;
    static int[] input; // 조합 사용

    static class Edge implements Comparable<Edge>{
        int from, to;
        double weight;
        public Edge(int from, int to, double weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
            return Double.compare(this.weight, o.weight);
        }
        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

    public static void main(String[] args) throws IOException {
        // 기본 셋팅
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        nodeList = new ArrayList<>();
        edgeList = new ArrayList<>();
        input = new int[2];

        // 노드 입력 받기
        for (int i = 0; i < V; i++) {
            st = new StringTokenizer(br.readLine());
            nodeList.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // 조합 사용
        comb(0, 0);

        Collections.sort(edgeList);
        make();
        // 미리 연결된 통로는 union 처리
        for (int i = 0; i < P; i++) {
            st = new StringTokenizer(br.readLine());
            union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        double weight = 0;
        for (Edge edge : edgeList) {
            if (!union(edge.from, edge.to)) continue;   // 만약 같은 집합이라면 통과
            weight += edge.weight;
        }

        System.out.printf("%.2f", weight);
    }

    // 노드로 2개의 조합 생성 후 각각의 거리를 계산하여 간선리스트에 추가
    public static void comb(int cnt, int start) {
        if (cnt == 2) {
            Point p1 = nodeList.get(input[0]);
            Point p2 = nodeList.get(input[1]);
            double weight = Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
            edgeList.add(new Edge(input[0] + 1, input[1] + 1, weight));
            return;
        }

        for (int i = start; i < nodeList.size(); i++) {
            input[cnt] = i;
            comb(cnt + 1, i + 1);
        }
    }

    // 자신을 대표자로 만들기
    public static void make() {
        parent = new int[V + 1];
        for (int i = 1; i < V + 1; i++) {
            parent[i] = i;
        }
    }

    // a가 속한 트리의 루트 찾기
    public static int find(int a) {
        if (a == parent[a]) return a;
        return parent[a] = find(parent[a]);
    }

    public static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot) return false;   // 같은 집합에 속함
        parent[bRoot] = aRoot;              // 합치기
        return true;
    }
}

 

---

 

3. 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());

        Point[] nodeArr = new Point[N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            nodeArr[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        boolean[] visited = new boolean[N + 1];
        double[] minEdge = new double[N + 1];
        Arrays.fill(minEdge, Double.MAX_VALUE);
        List<Integer>[] edgeList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++)
            edgeList[i] = new ArrayList<>();
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            edgeList[s].add(e);
            edgeList[e].add(s);
        }

        double result = 0;
        int cnt = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1, 0));
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if(visited[edge.e])
                continue;
            visited[edge.e] = true;
            result += edge.w;
            if(++cnt == N)
                break;
            Point nodeA = nodeArr[edge.e];
            for(int e : edgeList[edge.e])
                if(!visited[e]){
                    minEdge[e] = 0;
                    pq.offer(new Edge(e, 0));
                }
            for (int i = 2; i <= N; i++) {
                if(visited[i] || edge.e == i)
                    continue;
                Point nodeB = nodeArr[i];
                double distance = Math.sqrt(Math.pow(nodeA.x - nodeB.x, 2) + Math.pow(nodeA.y - nodeB.y, 2));
                if(minEdge[i] <= distance)
                    continue;
                minEdge[i] = distance;
                pq.offer(new Edge(i, distance));
            }

        }
        System.out.printf("%.2f", Math.round(result * 100) / 100.0);
    }

    static class Edge implements Comparable<Edge> {
        int e;
        double w;

        public Edge(int e, double w) {
            super();
            this.e = e;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return Double.compare(this.w, o.w);
        }
    }
}

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int n, m, p[];
    static List<Point> nodes;
    static List<Edge> edges;

    static class Edge implements Comparable<Edge> {
        int s;
        int e;
        double dist;

        Edge(int s, int e, double dist) {
            this.s = s;
            this.e = e;
            this.dist = dist;
        }

        public int compareTo(Edge o) {
            return Double.compare(this.dist, o.dist);
        }
    }

    static void makeSet() {
        p = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
    }

    static int find(int a) {
        if (a == p[a]) return a;
        return p[a] = find(p[a]);
    }

    static boolean union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return true;
        p[b] = a;
        return false;
    }

    static double getDistance(Point p1, Point p2) {
        return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        nodes = new ArrayList<>();
        edges = new ArrayList<>();
        nodes.add(null);
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            nodes.add(new Point(x, y));
        }

        makeSet();
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            union(s, e);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                edges.add(new Edge(i, j, getDistance(nodes.get(i), nodes.get(j))));
            }
        }

        Collections.sort(edges);
        double answer = 0.0;
        for (Edge edge : edges) {
            if (union(edge.s, edge.e)) continue;
            answer += edge.dist;
        }
        System.out.printf("%.2f", answer);
    }
}

 

---

 

4. 배운 점

- 모든 노드를 이으면서 최솟값을 구하기 위해서는 최소 신장 트리(크루스칼, 프림)을 사용해야 겠다.

- 다익스트라 알고리즘은 어느 정점에서 어느 정점까지의 최소 거리를 구하는 알고리즘이다.