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

문제 https://www.acmicpc.net/problem/14431 14431번: 소수마을 첫 번째 줄에 소수 마을의 위치 (X1,Y1)와 A마을의 위치 (X2,Y2)가 입력된다. 두 번째 줄에 경유할 수 있는 마을의 개수 N (0 ≤ N ≤ 4000)가 입력된다. 세 번째 줄부터 N+2번째 줄까지 경유 할 수 있는 마 www.acmicpc.net 풀이 이 문제는 소수를 구하는 알고리즘과 다익스트라 알고리즘을 이용해 해결할 수 있다. 1. 모든 정점들의 거리를 구하면서, 거리가 소수인 정점들만 연결한다. 2. 연결한 그래프를 다익스트라 알고리즘을 통해 최단거리를 계산한다. 이때 거리가 소수인지 판단하는 것은 에라토스테네스의 체 알고리즘을 사용해 미리 소수들을 구해놓았다. 코드 HTML 삽입 미리보기..

원문링크 : [백준] 14431 소수마을 (자바 풀이)