[Boj_14431] 소수마을

📎 문제 링크

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

 

▸ 문제

소수 마을들의 주민들은 매우 특이한 규칙을 준수한다. 규칙은 바로 “가고 싶은 위치까지의 거리가 소수일 경우에만 간다”라는 것이다. 소수 마을의 주민 승욱이는 소수 마을에서 멀리 떨어진 A마을에 볼일이 있어 그곳까지 가야한다. 소수 마을에서 A마을까지의 단숨에 가고 싶지만 안타깝게도 두 마을의 거리는 소수가 아닐 경우에는 그럴 수가 없다. 그럴 경우에는 다른 마을들을 경유하여 가야한다. (경유하는 마을도 현재 위치에서의 거리가 소수일 경우에만 갈 수 있다.) 소수 마을과 경유할 수 있는 마을들, 그리고 A마을의 위치가 좌표평면 상으로 주어질 때, 승욱이가 소수 마을의 규칙을 준수하여 A마을로 갈 수 있는 최단의 길을 찾는 것을 도와주자. 소수 판정을 위해 마을 간의 거리는 정수 부분만으로 취급한다. 예를 들어, 거리가 3.1415라면 이를 버림하여 3만 취급한다.

 

▸ 입력

첫 번째 줄에 소수 마을의 위치 (X1,Y1)와 A마을의 위치 (X2,Y2)가 입력된다. 두 번째 줄에 경유할 수 있는 마을의 개수 N (0 ≤ N ≤ 4000)가 입력된다. 세 번째 줄부터 N+2번째 줄까지 경유 할 수 있는 마을들의 위치 (X3,Y3)가 입력된다. 단, 각 마을들의 좌표는 절댓값이 3000을 넘지 않는 정수이다.

 

▸ 출력

소수 마을의 규칙을 준수하여 A마을까지 가는 방법 중 제일 짧은 거리로 갈 수 있는 길의 거리합을 출력한다. 만약 소수 마을의 규칙을 준수하여 갈 수 있는 방법이 없는 경우 -1을 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 3
• 🔔  문제 유형 : 수학, 그래프 이론, 정수론, 최단 경로, 데이크스트라, 소수 판정, 에라토스테네스의 체
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

소수 구하는 알고리즘과 다익스트라 알고리즘을 사용해서 풀 수 있는 문제이다.

 

먼저, 모든 정점들의 거리를 구하면서, 거리가 소수인 경우에만 정점들을 연결한다.

여기서 거리가 소수인지 판별하기 위해 에라토스테네스의 체 알고리즘을 사용해 미리 소수들을 구해놓았다.

 

연결한 그래프를 다익스트라 알고리즘을 사용하여 최단거리를 계산한다.

 

이때, 도착점이라면 거리를 리턴

도착점에 갈 수 있는 방법이 없다면 -1을 리턴한다.

 

✔ 최종 코드

메모리 : 90480KB
시간 : 360ms

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

public class Main {
    static int n;
    static ArrayList<Pos>[] arr;
    static public class Pos implements Comparable<Pos> {
        int end; int dist;
        public Pos (int end, int dist) {
            this.end = end; this.dist = dist;
        }
        @Override
        public int compareTo(Pos o) {
            return this.dist - o.dist;
        }
    }
    static final int INF = 987654321;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 에라스토테네스의 체
        // 소수 X true, 소수 O false
        boolean[] isPrime = new boolean[12001];
        isPrime[0] = isPrime[1] = true;
        for (int i = 2; i <= Math.sqrt(12000); i++) {
            if (!isPrime[i]) {
                for (int j = i*i; j <= 12000; j += i) {
                    isPrime[j] = true;
                }
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 소수 마을의 위치
        int sx = Integer.parseInt(st.nextToken());
        int sy = Integer.parseInt(st.nextToken());
        // A 마을의 위치
        int ex = Integer.parseInt(st.nextToken());
        int ey = Integer.parseInt(st.nextToken());

        n = Integer.parseInt(br.readLine())+2; // 경유할 수 있는 마을의 개수 + 시작점과 도착점

        arr = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new ArrayList<>();
        }

        ArrayList<int[]> list = new ArrayList<>();
        list.add(new int[]{sx, sy}); // 시작점
        for (int i = 0; i < n-2; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list.add(new int[]{u, v});
        }
        list.add(new int[]{ex, ey}); // 도착점

        // 모든 정점 간의 길이 구하기 - 소수인 경우만 연결
        for (int i = 0; i < list.size(); i++) {
            for (int j = i+1; j < list.size(); j++) {
                int cost = (int)(Math.sqrt(Math.pow(list.get(i)[0] - list.get(j)[0], 2)
                        + Math.pow(list.get(i)[1] - list.get(j)[1], 2)));

                if (isPrime[cost]) continue; // 소수 X

                arr[i].add(new Pos(j, cost));
                arr[j].add(new Pos(i, cost));
            }
        }

        int ans = dijkstra();

        System.out.println(ans);
    }

    private static int dijkstra() {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);

        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.offer(new Pos(0, 0));
        dist[0] = 0;

        while (!pq.isEmpty()) {
            Pos now = pq.poll();

            if (now.dist > dist[now.end]) continue;

            // 도착점이라면 거리 리턴
            if (now.end == n-1) return dist[n-1];

            for (int i = 0; i < arr[now.end].size(); i++) {
                int nextEnd = arr[now.end].get(i).end;
                int nextDist = arr[now.end].get(i).dist;

                if (dist[nextEnd] > dist[now.end] + nextDist) {
                    dist[nextEnd] = dist[now.end] + nextDist;
                    pq.offer(new Pos(nextEnd, dist[nextEnd]));
                }
            }
        }

        return -1;
    }
}

 

해결 완료 ! 🔥