1774번 - 우주신과의 교감

2024-05-15

#JAVA#백준

문제 링크

문제 풀이 시간 : 3시간

문제 요약

•
황선자씨는 N-1명의 우주신과 교감을 할 수 있다.
황선자씨

•
황선자씨나 우주신들이 연결된 통로 M개가 존재한다.

•
아직 연결되지 않은 우주신들이 연결되기 위해 필요한 통로의 최소 길이를 구하라

문제 풀이

문제를 읽다가 재밌어 보여서 풀기 시작했는데

풀다 보니 얼마 전에 알고리즘 수업 시간에 배웠던 최소 신장 트리(MST) 문제라는 것을 깨달았다.

그래서 Prim의 알고리즘으로 풀려고 시도를 했는데….

초기 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static class Pair {
        private int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static int N;
    public static int M;
    public static ArrayList<Pair> gods;
    public static ArrayList<Integer> road;

    public static double value[][];
    public static double result;

    public static void find() { //프림의 알고리즘
        if (road.size() == N)
            return;
        double min = Double.MAX_VALUE;
        int min_idx = -1;
        for (int i = 0; i < road.size(); i++) { //현재 연결된 우주신들과 연결되지 않은 우주신 사이에 가장 짧은 통로 찾기
            for (int j = 0; j < N; j++) {
                if(j==road.get(i))
                    continue;
                if(road.contains(j))
                    continue;
                if(value[road.get(i)][j]<min){
                    min = value[road.get(i)][j];
                    min_idx = j;
                }
            }
        }
        road.add(min_idx); //새로 연결된 우주신 넣기
        result += min; //최소 길이 추가
        find(); //재귀
    }


    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());
        gods = new ArrayList<>();
        road = new ArrayList<>();
        int x, y;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            gods.add(new Pair(x, y));
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            road.add(Integer.parseInt(st.nextToken())-1);
            road.add(Integer.parseInt(st.nextToken())-1);
        }
        value = new double[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                value[i][j] = Math.sqrt(Math.pow((gods.get(i).x - gods.get(j).x), 2) + Math.pow((gods.get(i).y - gods.get(j).y), 2));
            }
        }
        result = 0;
        find();
        System.out.println(result);
    }
}

얼레?

예상은 했지만 바로 시간 초과가 나왔다.

확실히 조행래 교수님이 알려주신 방법대로 안 해서 그런가?

하고 배운 대로 풀어보려고 코드를 다시 짜봤다.

중기 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static class Pair {
        private int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static int N;
    public static int M;
    public static ArrayList<Pair> gods;
    public static ArrayList<Integer> road;
    public static int nearest[];
    public static double value[][];
    public static double result;

    public static void find() {
        if (road.size() == N)
            return;
        double min = Double.MAX_VALUE;
        int min_idx = -1;
        for(int i=0;i<N;i++){ 
            if(road.contains(i)) //연결된 우주신은 패스
                continue;

            if(value[i][nearest[i]]<min){ //최소 길이 찾기
                min = value[i][nearest[i]];
                min_idx = i;
            }
        }
        result+=Math.sqrt(min);
        road.add(min_idx);//새로 찾은 우주신 넣기
        resetNearest();//nearest 다시 초기화
        find();
    }

    public static void resetNearest(){ //nearest배열 초기화 함수
        for(int i=0;i<N;i++) {
            if (road.contains(i))
                continue;
            int near = -1;
            double near_num = Double.MAX_VALUE;
            for (int j = 0; j < N; j++) { //연결된 우주신들 중 j우주신과 가장 가까운 우주신 찾기
                if (i == j)
                    continue;
                if (road.contains(j)) {
                    if (value[i][j] < near_num) {
                        near_num = value[i][j];
                        near = j;
                    }
                }
            }
            nearest[i] = near;
        }
    }


    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());
        gods = new ArrayList<>();
        road = new ArrayList<>();
        nearest = new int[N];
        int x, y;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            gods.add(new Pair(x, y));
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            road.add(Integer.parseInt(st.nextToken())-1);
            road.add(Integer.parseInt(st.nextToken())-1);
        }
        value = new double[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                value[i][j] = Math.pow((gods.get(i).x - gods.get(j).x), 2) + Math.pow((gods.get(i).y - gods.get(j).y), 2);
                value[j][i] = value[i][j];
            }
        }
        resetNearest(); //nearest 배열 초기화

        result = 0;
        find();
        System.out.println(result);
    }
}

이렇게 해도 똑같이 시간 초과가 나버려서

결국 다른 사람의 풀이를 참조할 수 밖에 없었다..

최종 코드

Java

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

public class Main {
		//우선순위 큐에서 사용하기 위한 클래스
    static class Path implements Comparable<Path> {
        int vertex;
        double weight;

        Path(int vertex, double weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compareTo(Path other) {
            return Double.compare(this.weight, other.weight);
        }
    }
		//엣지 클래스
    static class Edge {
        int from, to;
        double weight;

        Edge(int from, int to, double weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
		//프림 알고리즘
    public static double find(List<List<Edge>> edges, int N) {
        boolean[] connected = new boolean[N]; //현재 연결된 우주신들
        double[] minWeight = new double[N]; //각 우주신들의 최소 거리
        //시작 노드를 제외하고 모든 노드 가중치 무한대
        for (int i = 1; i < N; i++) {
            minWeight[i] = Double.MAX_VALUE;
        }
				
        PriorityQueue<Path> pq = new PriorityQueue<>();
        pq.add(new Path(0, 0));
        double result = 0;

        while (!pq.isEmpty()) {
            Path path = pq.poll();
            int god = path.vertex;
            double weight = path.weight;
						//이미 연결된 우주신이면 패스
            if (connected[god]) continue;
            //현재 우주신을 연결시킴
            connected[god] = true;
            //현재 우주신의 최소 거리를 결과에 추가
            result += weight;
						//현재 우주신과 다른 우주신들 사이 거리 검사
            for (Edge edge : edges.get(god)) {
		            //연결되지 않은 우주신들의 최소 거리 업데이트
                if (!connected[edge.to] && minWeight[edge.to] > edge.weight) {
                    minWeight[edge.to] = edge.weight;
                    pq.add(new Path(edge.to, edge.weight));
                }
            }
        }

        return result;    
    }

    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());
        int M = Integer.parseInt(st.nextToken());
        long[][] coordinates = new long[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            coordinates[i][0] = Long.parseLong(st.nextToken());
            coordinates[i][1] = Long.parseLong(st.nextToken());
        }

        List<List<Edge>> edges = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            edges.add(new LinkedList<>());
        }
				//이미 연결된 우주신들 사이의 거리 0으로 설정
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            edges.get(from).add(new Edge(from, to, 0));
            edges.get(to).add(new Edge(to, from, 0));
        }
				//모든 우주신들 사이 거리 계산, 추가
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                double weight = Math.sqrt(Math.pow(coordinates[j][0] - coordinates[i][0], 2) +
                        Math.pow(coordinates[j][1] - coordinates[i][1], 2));
                edges.get(i).add(new Edge(i, j, weight));
                edges.get(j).add(new Edge(j, i, weight));
            }
        }

        System.out.printf("%.2f", find(edges, N));
    }
}

교수님 말대로 생각으로 하는 거랑 구현은 하늘과 땅 차이인 것 같다.

구현을 많이 해보자…