BOJ 14431 - 소수마을 링크
(2023.04.24 기준 G3)

문제

소수 마을의 위치, 가고자 하는 A마을의 위치, 경유할 수 있는 N개의 마을의 위치가 좌표평면 상으로 주어진다. 마을 간의 거리는 정수 부분만으로 취급하고 거리가 소수인 경우에만 갈 수 있다 하면, 제일 짧은 거리로 갈 수 있는 길의 거리합 출력

알고리즘

두 점의 거리를 전부 구해 소수인지 판정하여 간선을 연결하여 다익스트라.

풀이

마을 간 거리는 정수 부분만으로 취급한다고 했으니 유클리드 거리를 구해 소수점 밑으로 전부 버림하여 정수로 나타내자.
이 정수가 소수여야 한다. 마을의 좌표의 절댓값의 최대는 3,000. 가능한 최대 거리는 (-3000, -3000), (3000, 3000)의 거리인 8,485가 된다. 그러면 8,485 까지 소수 판정이 가능해야 하므로 충분히 에라토스테네스의 체로 가능하다.

그럼 이제 간단하다. 각 마을 간의 거리를 구해 소수인지 판정하고, 만약 소수이면 그 두 마을을 잇는 간선을 그래프에 추가하는 것이다. 모든 마을 쌍을 살펴보았으면 이제 그래프로 다익스트라를 돌리면 된다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;
typedef priority_queue<pii, vector<pii>, greater<pii>> heapq;
const int inf = 1e9;

int distance(pii a, pii b){ // 거리
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // 에라토스테네스의 체
    int MAX = 8485; // dist((-3000, -3000), (3000, 3000)) = 8485
    bool is_prime[MAX + 1];
    fill(is_prime + 2, is_prime + MAX + 1, true);
    for (int i = 2, LIM = sqrt(MAX) + 1; i < LIM; i++)
        if (is_prime[i])
            for (int j = i * i; j <= MAX; j += i)
                is_prime[j] = false;

    // 모든 위치를 합치자.
    int X1, Y1, X2, Y2;
    cin >> X1 >> Y1 >> X2 >> Y2;
    vector<pii> pos = {{X1, Y1}, {X2, Y2}}; // 0번은 시작점, 1번은 도착점

    int N, X, Y;
    cin >> N;
    while (N--) cin >> X >> Y, pos.push_back({X, Y});

    // 각 마을 쌍의 거리를 계산하여 소수인 경우에만 간선 추가
    N = pos.size();
    vector<pii> graph[N];
    for (int i = 0, d; i < N - 1; i++) for (int j = i + 1; j < N; j++){
        d = distance(pos[i], pos[j]);
        if (is_prime[d]) graph[i].push_back({j, d}), graph[j].push_back({i, d});
    }

    // 다익스트라
    heapq pq;
    pq.push({0, 0});
    int distance[N];
    distance[0] = 0, fill(distance + 1, distance + N, inf);
    while (!pq.empty()){
        pii here = pq.top(); pq.pop();
        if (distance[here.y] < here.x) continue;
        for (pii there: graph[here.y]) if (distance[there.x] > here.x + there.y)
            distance[there.x] = here.x + there.y, pq.push({distance[there.x], there.x});
    }

    if (distance[1] < inf) cout << distance[1];
    else cout << -1;
}

• Python

import sys; input = sys.stdin.readline
from math import floor, inf
from heapq import heappop, heappush

def dist(a, b): # 거리
    return floor(((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5)

# 에라토스테네스의 체
MAX = 8485 # dist((-3000, -3000), (3000, 3000)) = 8485
is_prime = [True] * (MAX + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, floor(MAX ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i ** 2, MAX + 1, i):
            is_prime[j] = False

# 모든 위치를 합치자.
X1, Y1, X2, Y2 = map(int, input().split())
pos = [(X1, Y1), (X2, Y2)] # 0번은 시작점, 1번은 도착점

for _ in range(int(input())):
    pos.append(tuple(map(int, input().split())))

# 각 마을 쌍의 거리를 계산하여 소수인 경우에만 간선 추가
N = len(pos)
graph = [[] for _ in range(N)]
for i in range(N - 1):
    for j in range(i + 1, N):
        d = dist(pos[i], pos[j])
        if is_prime[d]:
            graph[i].append((j, d))
            graph[j].append((i, d))

# 다익스트라
queue = [(0, 0)]
distance = [inf] * N
distance[0] = 0
while queue:
    d, i = heappop(queue)
    if distance[i] < d:
        continue
    for j, dd in graph[i]:
        if distance[j] > d + dd:
            distance[j] = d + dd
            heappush(queue, (distance[j], j))

print(distance[1]) if distance[1] < inf else print(-1)