[백준] 14431 소수마을 (자바 풀이)
- 알고리즘 문제 해결(PS)/[백준]
- 2022. 2. 25.
문제
https://www.acmicpc.net/problem/14431
풀이
이 문제는 소수를 구하는 알고리즘과 다익스트라 알고리즘을 이용해 해결할 수 있다.
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 |
결과
푸는데 꽤 애를 먹었다. 알고보니 소수를 구하는 알고리즘에서 0,1을 체크하지 않은 실수를 저질렀다.
반응형
'알고리즘 문제 해결(PS) > [백준]' 카테고리의 다른 글
[백준] 17136번 색종이 붙이기 (자바 풀이) (0) | 2022.03.03 |
---|---|
[백준] 11286번 절댓값 힙 (자바 풀이) (0) | 2022.03.02 |
[백준] 1644번 소수의 연속합 (자바 풀이) (0) | 2022.02.23 |
[백준] 1531번 투명 (자바풀이) (0) | 2022.02.18 |
[백준] 1111번 IQ Test (자바 풀이) (0) | 2022.02.16 |