14431. 소수마을#
관찰#
문제는 명확하게
마을 좌표 간 거리가 소수인 점만 연결한 그래프에서,
시작 마을에서 도착 마을까지 갈 수 있는 최단 거리를 구하는 문제이다.
에라토스테네스의 체와, 다익스트라를 각각 사용해 문제를 해결할 수 있다고 판단했다.
시간 복잡도#
좌표 평면 크기: \( |K| \le 3000 \)
마을의 개수: \( 0 \le N \le 4000 \)
에라스토테네스의 체#
두 점 사이의 최대 거리는 \( \sqrt{6000^2 + 6000^2} \approx 8490 \) 이므로,
그 이하의 정수에 대해 소수 여부를 미리 계산한다.
이 때의 시간복잡도는 \( O(M \log \log M) \)로, 전체 시간에서 무시 가능한 수준이다.
다익스트라#
모든 마을 쌍에 대해 거리를 계산하여,
거리가 소수인 경우에만 간선을 연결한 완전 그래프 형태로 탐색한다.
정점 수: \( N \)
간선 수: 최악의 경우 \( O(N^2) \)
다익스트라 알고리즘을 우선순위 큐로 구현하면
\( O(N^2 \log N) \)의 시간복잡도가 발생하기에,
최악의 경우 \( 4000 * 4000 * \log 4000\approx 1.6 \times 10^7 \times 12 \approx 2 \times 10^8 \) 번의 연산이 이루어진다.
하지만,
모든 거리 값이 소수가 될 확률이 매우 낮고,
따라서 유효한 간선 수가 크게 줄어들기 때문에
실제 수행 시간은 최악의 경우보다 훨씬 작아질 것이다.
시행착오#
초기 구현은 Go 기준 720ms 수준에서 통과했으나,
몇가지의 최적화를 통해 48ms까지 줄일 수 있었다.
1. math.Pow() 미사용#
Go 의 math 라이브러리는 대부분의 연산에서 float64 연산을 사용하고,
이로 인해 내부적으로 부동소수점 연산을 수행한다.
이는 빈번한 호출 시 불필요한 오버헤드가 발생하기 때문에,
유클리드 거리를 계산할 때 식을 그대로
math.Sqrt(math.Pow(dx, 2) + math.Pow(dy, 2))math.Sqrt(dx*dx + dy*dy)720ms에서 116ms로 유의미하게 시간을 줄일 수 있었다.
2. 그래프 저장 대신 즉석에서 간선 비교#
초기 풀이에서는
모든 정점 쌍에 대해 간선을 미리 생성해 인접 리스트를 구성했으나,
메모리 사용량 증가와 함께 불필요한 간선 생성 비용이 발생했다.
이를 개선해,
다익스트라 탐색 과정에서 현재 정점 기준으로 모든 다른 정점과의 거리만 즉석에서 계산하고,
그 거리가 소수인 경우에만 비교를 수행하도록 변경했다.
이로 인해 추가 메모리 사용을 줄이고, 실제로 탐색되는 간선만 계산하게 만들어 전체 실행 시간과 메모리 사용량을 크게 줄이는 효과가 있었다.
시간에서는 116ms -> 48ms 로,
메모리 사용량 또한 57212KB -> 1960KB 로 유의미하게 개선되었다.
(번외). a*#
해당 문제의 시간 기준 1등의 풀이는 a* 알고리즘 기반으로 되어 있다.
휴리스틱 기반이기에 PS에 사용될 것이라고 생각 못했었고,
실제로 사용되는건 처음 봤는데, 나중에 직접 한 번 구현해봐야겠다고 생각했다.