알고리즘 문제 해결(PS)/[백준]

[백준] 14431 소수마을 (자바 풀이)

연구소장 J 2022. 2. 25. 11:45

문제

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

 

14431번: 소수마을

첫 번째 줄에 소수 마을의 위치 (X1,Y1)와 A마을의 위치 (X2,Y2)가 입력된다. 두 번째 줄에 경유할 수 있는 마을의 개수 N (0 ≤ N ≤ 4000)가 입력된다. 세 번째 줄부터 N+2번째 줄까지 경유 할 수 있는 마

www.acmicpc.net

풀이

이 문제는 소수를 구하는 알고리즘과 다익스트라 알고리즘을 이용해 해결할 수 있다.

 

1. 모든 정점들의 거리를 구하면서, 거리가 소수인 정점들만 연결한다.

2. 연결한 그래프를 다익스트라 알고리즘을 통해 최단거리를 계산한다.

 

이때 거리가 소수인지 판단하는 것은 에라토스테네스의 체 알고리즘을 사용해 미리 소수들을 구해놓았다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.io.*;
import java.util.*;
 
public class Baekjoon_14431 {
    static int sx,sy,ex,ey, N;
    static ArrayList<Node> graph[];
    static boolean prime[];
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sx = Integer.parseInt(st.nextToken());
        sy = Integer.parseInt(st.nextToken());
        ex = Integer.parseInt(st.nextToken());
        ey = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N+2];
        for(int i=0; i<N+2; i++) {
            graph[i] = new ArrayList<>();
        }
        ArrayList<Node> temp = new ArrayList<>();
        temp.add(new Node(sx,sy));    // 시작점 추가
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            temp.add(new Node(x,y));
        }
        temp.add(new Node(ex,ey));    // 끝점 추가
        
        /* 에라토스테네스의 체를 이용한 소수 구하기 */
        prime = new boolean[12001];
        getPrime();
        
        /* 모든 정점 간의 길이 구하기 - 소수인 경우에만 연결 */
        for(int i=0; i< temp.size() ; i++) {
            for(int j=i+1; j< temp.size(); j++) {
                int dis = getDis(temp.get(i).x, temp.get(i).w, temp.get(j).x, temp.get(j).w);
                if(!prime[dis]) {    // 거리가 소수라면
                    graph[i].add(new Node(j,dis));
                    graph[j].add(new Node(i,dis));
                }
            }
        }
        dijkstra();
    }
    
    /* 에라토스테네스의 체 이용하여 소수 구하기 */
    static void getPrime() {
        prime[0= true;
        prime[1= true;
        for(int i=2; i*i<=12000; i++) {
            if(!prime[i]) {
                for(int j=i+i; j<=12000; j += i) {
                    prime[j] = true;
                }
            }
        }
    }
    
    static int getDis(int x1, int y1, int x2, int y2) {
        return (int) Math.sqrt( (int)Math.pow((x2-x1), 2+ (int)Math.pow(y2-y1, 2));
    }
    
    static class Node{
        int x;
        int w;
        Node(int x, int w){
            this.x = x;
            this.w = w;
        }
        
    }
    
    /* 다익스트라 알고리즘 */
    static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>( (o1,o2) -> o1.w-o2.w );
        pq.add(new Node(0,0));
        
        int dis[] = new int[N+2];
        Arrays.fill(dis, 1000000000);
        dis[0= 0;    
        
        while(!pq.isEmpty()) {
            int cur = pq.peek().x;
            int curW = pq.poll().w;        
            if(curW > dis[cur]) continue;
            for(int i=0; i<graph[cur].size(); i++) {
                int next = graph[cur].get(i).x;
                int nextW = graph[cur].get(i).w;
                if(dis[next] > dis[cur] + nextW) {
                    dis[next] = dis[cur]+nextW;
                    pq.add(new Node(next,dis[next]));
                }
            }
        }
        
        if(dis[N+1== 1000000000) {
            System.out.println(-1);
        }else {
            System.out.println(dis[N+1]);
        }
    }
 
}
cs

 

결과

백준 14431

푸는데 꽤 애를 먹었다. 알고보니 소수를 구하는 알고리즘에서 0,1을 체크하지 않은 실수를 저질렀다.

 

반응형