728x90
반응형
문제
저작권 문제로 인해 링크만 첨부합니다.
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE&problemTitle=1251&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
풀이 방법
프림 알고리즘에 대한 개념을 배우고 풀어본 문제다.
우선 입력값을 이요해서 인접 행렬을 만들어주고, 만들면서 각 섬 사이의 거리 값도 저장해줬다.
그 후 이제 프림 알고리즘을 수행했다.
아직 방문하지 않은 섬들중에서 가장 최소 거리인 섬을 찾고 최소 거리와 그 섬의 인덱스를 찾는다.
그 후 방문 처리를 한 후에 환경부담금 계산 후 결과변수에 더해준다.
이제 인접 배열을 사용해서 갈 수 있는 섬들의 거리를 업데이트 해주고 섬의 개수만큼 같은 작업을 반복해줬다.
제출 코드
import java.io.*;
import java.util.*;
public class D4_1251_하나로 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for (int test_case = 1; test_case <= T; test_case++) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
double[] minDist = new double[N];
boolean[] visited = new boolean[N]; //체크여부
int[] x = new int[N];
int[] y = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
x[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
y[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
double E = Double.parseDouble(st.nextToken());
double[][] adjMatrix = new double[N][N]; //인접행렬
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) { //인접 행렬에 각 섬 사이의 거리 값 저장
if(x[i]== x[j] || y[i] ==y[j])
adjMatrix[i][j] = Math.abs(x[i] - x[j]) + Math.abs(y[i] - y[j]);
else adjMatrix[i][j] = Math.sqrt( Math.pow(x[i]-x[j],2)+Math.pow(y[i]-y[j],2) );
}
minDist[i] = Integer.MAX_VALUE;
}
//프림 알고리즘
minDist[0] = 0;
double ans = 0;
for (int c = 0; c < adjMatrix.length; c++) {
double min = Integer.MAX_VALUE;
int minVertex = -1;
for (int i = 0; i < N; i++) {
if(!visited[i]&&min > minDist[i]) { //가장 최소 거리 찾기
min = minDist[i];
minVertex = i;
}
}
visited[minVertex] = true;
ans+= E * min*min; //환경부담금 계산 후 더하기
for (int i = 0; i < N; i++) {
if(!visited[i]&& minDist[i]> adjMatrix[minVertex][i]) { //갈 수 있는 섬들 업데이트
minDist[i] = adjMatrix[minVertex][i];
}
}
}
System.out.printf("#%d %.0f\n",test_case, ans);
}
}
}
728x90
반응형
'알고리즘 > SWEA' 카테고리의 다른 글
[SWEA] D4 3289 서로소 집합 (JAVA) (0) | 2022.03.11 |
---|---|
[SWEA] D4 1238 Contact (JAVA) (0) | 2022.03.09 |
[SWEA] D4 7465 창용 마을 무리의 개수 (JAVA) (0) | 2022.03.06 |
[SWEA] D4 3234 준환이의 양팔저울 (0) | 2022.02.18 |
[SWEA] 0217 알고리즘 문제풀이(D5_1247_최적경로) (0) | 2022.02.17 |