[BOJ/Python] 14431_소수마을

문제출처:https://www.acmicpc.net/problem/14431

14431번: 소수마을

 

문제

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

입력

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

출력

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

예제 입력 1

1 2 5 4
2
4 1
6 2

예제 출력 1

6

예제 입력 2

1 2 5 4
0

예제 출력 2

-1

힌트

 

---

풀이

 

1. 소수 마을 에서 A마을까지 소수의 경로를 이용하여 이동할 수 있는지를 확인하는 문제이다.
2. 마을 사이의 거리가 소수인 경우에만 이동이 가능하며, 마을들을 경유하여 A마을까지 이동할 수 있는지 여부를 확인하면 된다.
3. 이때 소수의 경로로 이동할 수 있다면, 그 최단거리를 출력하면 된다.

 

코드는 다음과 같다.

 

import sys
import math
import heapq
 
INF = int(1e9)
def dijkstra():
    queue = []
    distance[0] = 0
    heapq.heappush(queue,(0,0))
 
    while queue:
        dist,node = heapq.heappop(queue)
 
        if node == 1:
            return dist
 
        if distance[node] < dist:
            continue
 
        for next in graph[node]:
            cost = dist + next[1]
            if distance[next[0]] > cost:
                distance[next[0]] = cost
                heapq.heappush(queue,(cost,next[0]))
 
    return -1
 
 
num = [True for _ in range(9000)]
prime_numbers=set()
for i in range(2,9000):
    if num[i]==True:
        prime_numbers.add(i)
        for j in range(i,9000,i):
            num[j]=False
 
x1,y1,x2,y2 = map(int,sys.stdin.readline().split())
n = int(sys.stdin.readline())
graph = [[] for _ in range(n+2)]
distance = [INF for _ in range(n+2)]
town = [(x1,y1),(x2,y2)]
for _ in range(n):
    town.append(tuple(map(int,sys.stdin.readline().split())))
 
for i in range(n+2):
    for j in range(i+1,n+2):
        dist = int(math.dist(town[i],town[j]))
        if dist in prime_numbers:
            graph[i].append((j,dist))
            graph[j].append((i,dist))
 
print(dijkstra())

 

1. 우선 마을사이의 거리가 소수인지 확인하기 위하여 에라토스테네스의 체를 이용하여 9000 이하의 소수들을 구하였다. (좌표의 절댓값이 3000 이하이므로, 제일 먼 두 마을 사이의 거리는 (6000 * root2) < 9000 이 되므로 9000 이하의 소수들을 구하였다.)
2. 소수 마을은 0번 노드, 목적지인 A 마을은 1번 노드이다.
3. 모든 마을들 사이의 거리를 구하고, 그 거리가 소수라면 graph에 두 마을 사이의 간선 정보를 추가한다.
4. graph를 이용하여 다익스트라 알고리즘을 수행한다.
5. 만약 목적지인 A마을에 도달한다면, 그 거리를 반환한다.
6. 만약 다익스트라 알고리즘을 수행하였지만, A마을에 도달하지 못한다면 -1을 반환한다.
7. 반환값을 출력한다.