접근방법
기본적인 접근방법
Prim 알고리즘을 이용한 인접 행렬
각 노드로 연결되는 최소 거리를 minEdge 배열로 생성한 후 값을 무한대로 초기화한다.
0번 노드에서 시작해서 연결할 수 있는 모든 노드들의 거리를 계산해서 minEdge를 갱신한다.
갱신한 값 중에서 제일 작은 노드를 고른 다음 반복한다.
이런 순서로 알고리즘이 진행되게 된다.
이 방법의 경우 시간 복잡도는 V^2이 된다.
추가적인 접근방법
Prim 알고리즘을 이용한 인접 행렬 + PriorityQueue
PriorityQueue를 쓰지 않은 방법과 다른 것은 minEdge를 갱신할 때 PriorityQueue의 offer( ) 하는 것과
제일 작은 노드를 구할 때는 PriorityQueue의 poll( )을 한다는 것이다.
이 방법의 경우 시간 복잡도는 (E + V) log V이다.
이렇게 보면 이 방법이 더 빠른거 같지만 이 문제의 경우 간선이 모든 노드끼리 연결되어 있으므로 E = V^2이다.
그러므로 시간 복잡도는 (V^2 + V) log V이다.
정말로 PriorityQueue를 이용한 방법이 더 느린지 살펴보겠다.
코드
인접행렬
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class EA1251_인접행렬 {
static int N, visitIsland;
static boolean[] visited;
static double[] minEdge;
static long[][] pos;
static double[][] disMatrix;
static double ans;
static double E;
static class Dis implements Comparable<Dis>{
double len;
int idx;
public Dis(double len, int idx) {
super();
this.len = len;
this.idx = idx;
}
@Override
public int compareTo(Dis o) {
if(this.len < o.len) return -1;
else if(this.len > o.len) return 1;
return 0;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
long beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
//pos 배열 2, N
pos = new long[N][2];
for (int i = 0; i < 2; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
pos[j][i] = Integer.parseInt(st.nextToken());
}
}
E = Double.parseDouble(br.readLine());
ans = 0;
visitIsland = 1;
visited = new boolean[N];
// 모든 거리 계산
disMatrix = new double[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
disMatrix[i][j] = disMatrix[j][i] = calcLength(i, j);
}
}
minEdge = new double[N];
Arrays.fill(minEdge, Double.MAX_VALUE);
minEdge[0] = 0;
while(visitIsland <= N) {
double min = Double.MAX_VALUE;
int minNo = 0;
// minEdge에서 최솟값 찾기
for (int i = 0; i < N; i++) {
if(!visited[i] && min > minEdge[i]){
min = minEdge[i];
minNo = i;
}
}
// 신장 트리에 포함
visited[minNo] = true;
ans += min * min;
// 현재 최소 거리 갱신
for (int i = 0; i < N; i++) {
if(!visited[i] && minEdge[i] > disMatrix[minNo][i]){
minEdge[i] = disMatrix[minNo][i];
}
}
visitIsland++;
}
sb.append("#" + tc + " " + Math.round(ans * E) + '\n');
}
System.out.print(sb.toString());
long afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
long secDiffTime = (afterTime - beforeTime); //두 시간에 차 계산
System.out.println("시간차이(ms) : "+secDiffTime);
}
private static double calcLength(int firIdx, int secIdx) {
double len;
len = Math.sqrt( (pos[firIdx][0] - pos[secIdx][0]) * (pos[firIdx][0] - pos[secIdx][0]) +
(pos[firIdx][1] - pos[secIdx][1]) * (pos[firIdx][1] - pos[secIdx][1]));
return len;
}
}
인접행렬 + PriorityQueue
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class EA1251_PQ {
static int N, visitIsland;
static boolean[] visited;
static double[] minEdge;
static long[][] pos;
static double[][] disMatrix;
static PriorityQueue<Dis> que;
static double ans;
static double E;
static class Dis implements Comparable<Dis>{
double len;
int idx;
public Dis(double len, int idx) {
super();
this.len = len;
this.idx = idx;
}
@Override
public int compareTo(Dis o) {
if(this.len < o.len) return -1;
else if(this.len > o.len) return 1;
return 0;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
long beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
//pos 배열 2, N
pos = new long[N][2];
for (int i = 0; i < 2; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
pos[j][i] = Integer.parseInt(st.nextToken());
}
}
E = Double.parseDouble(br.readLine());
ans = 0;
visitIsland = 1;
visited = new boolean[N];
// 모든 거리 계산
disMatrix = new double[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
disMatrix[i][j] = disMatrix[j][i] = calcLength(i, j);
}
}
minEdge = new double[N];
Arrays.fill(minEdge, Double.MAX_VALUE);
minEdge[0] = 0;
que = new PriorityQueue<>();
que.offer(new Dis(minEdge[0], 0));
while(visitIsland <= N) {
Dis dis;
do {
dis = que.poll();
} while (visited[dis.idx]);
// 신장 트리에 포함
visited[dis.idx] = true;
ans += dis.len * dis.len;
// 현재 최소 거리 갱신
for (int i = 0; i < N; i++) {
if(!visited[i] && minEdge[i] > disMatrix[dis.idx][i]){
minEdge[i] = disMatrix[dis.idx][i];
que.offer(new Dis(minEdge[i], i));
}
}
visitIsland++;
}
sb.append("#" + tc + " " + Math.round(ans * E) + '\n');
}
System.out.print(sb.toString());
long afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
long secDiffTime = (afterTime - beforeTime); //두 시간에 차 계산
System.out.println("시간차이(ms) : "+secDiffTime);
}
private static double calcLength(int firIdx, int secIdx) {
double len;
len = Math.sqrt( (pos[firIdx][0] - pos[secIdx][0]) * (pos[firIdx][0] - pos[secIdx][0]) +
(pos[firIdx][1] - pos[secIdx][1]) * (pos[firIdx][1] - pos[secIdx][1]));
return len;
}
}
이 두 가지 코드에 testinput 중에서 N = 1000인 case를 100번 실행한 후 몇 초 만에 실행되었는지 비교하였다.
실제로 PriorityQueue를 이용한 방법이 조금 늦게 실행되었다.
'코딩테스트 > SWEA' 카테고리의 다른 글
| SWEA 1225 : 암호생성기 (0) | 2021.02.04 |
|---|