[JAVA] 1251번 하나로

[JAVA] 1251번 하나로

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

풀이

보급로 문제와 비슷하게 우선순위 큐를 사용해 문제를 풀이하였다.

좌표 형태로 값이 주어지기 때문에, 각 섬 간의 거리를 저장하고 그 값으로 비교를 하여 우선순위를 정하도록 하였다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringTokenizer; class Node implements Comparable{ int land; long dist; Node(int land, long dist) { this.land = land; this.dist = dist; } // 우선순위 큐 비교 @Override public int compareTo(Node n) { return Long.compare(this.dist, n.dist); } } public class SWEA1251_하나로 { static int N; static double E; static int arrX[]; static int arrY[]; static Queue q; static List l[]; static boolean visited[]; static long result; public static void solve(int cnt) { while(!q.isEmpty()) { Node v = q.poll(); if (visited[v.land]) continue; visited[v.land] = true; result += v.dist; if (++cnt == N) return; for (int i = 0; i < l[v.land].size(); i++) { Node to = l[v.land].get(i); if (!visited[to.land]) q.add(to); } } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer stX; StringTokenizer stY; int T = Integer.parseInt(br.readLine()); for (int tc = 1; tc <= T; tc++) { N = Integer.parseInt(br.readLine()); arrX = new int[N]; arrY = new int[N]; q = new PriorityQueue<>(); l = new ArrayList[N]; visited = new boolean[N]; result = 0; for (int i = 0; i < N; i++) l[i] = new ArrayList<>(); stX = new StringTokenizer(br.readLine()); stY = new StringTokenizer(br.readLine()); E = Double.parseDouble(br.readLine()); for (int i = 0; i < N; i++) { arrX[i] = Integer.parseInt(stX.nextToken()); arrY[i] = Integer.parseInt(stY.nextToken()); } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i != j) { l[i].add(new Node(j, (long) (Math.pow(arrX[i] - arrX[j], 2) + Math.pow(arrY[i] - arrY[j], 2)))); } } } q.add(new Node(0, 0)); solve(0); System.out.println("#" + tc + " " + Math.round(result * E)); } } }

from http://pekahblog.tistory.com/159 by ccl(S) rewrite - 2021-09-23 08:01:57