[SWEA] 1251 하나로 - JAVA

1. 문제

SW Expert Academy

환경 부담금 = 환경 부담 세율(E)과 각 해저터널 길이(L)의 제곱의 곱(E * L^2)

총 환경 부담금을 최소로 지불하며, N개의 모든 섬을 연결할 수 있는 교통 시스템을 설계하시오.

---

2. 풀이

Connect 클래스

• 인덱스와 길이의 타입이 달라서 클래스를 만들어주었다. 만든 김에 Comparable 클래스를 상속받아서 PriorityQueue에 써먹었다.

static class Connect implements Comparable<Connect> {
   int idx;
   long length;

   private Connect(int idx, long length) {
      this.idx = idx;
      this.length = length;
   }

   @Override
   public int compareTo(Connect o) {
      return Long.valueOf(this.length).compareTo(o.length);
   }
}

 

변수들

• 테스트케이스와 상관없이 꼭 필요한 변수들을 위에 선언해놓았다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;

int T = Integer.parseInt(in.readLine());

int N;
int[][] island;
long[] distance;
boolean[] visited;
double E, cost;

PriorityQueue<Connect> pQueue = new PriorityQueue<>();

 

다익스트라를 위한 초기 설정들

• 테스트케이스마다 초기화해준 변수들이다. 
• PriorityQueue는 어차피 테스트케이스가 끝날때 비워진 상태이므로 새로 객체를 생성하지 않고 위에서 만든 객체를 그대로 썼다.

N = Integer.parseInt(in.readLine());
island = new int[N][2];

st = new StringTokenizer(in.readLine());
for (int n = 0; n < N; n++) island[n][0] = Integer.parseInt(st.nextToken());

st = new StringTokenizer(in.readLine());
for (int n = 0; n < N; n++) island[n][1] = Integer.parseInt(st.nextToken());

E = Double.parseDouble(in.readLine());
cost = 0;

visited = new boolean[N];
distance = new long[N];
Arrays.fill(distance, Long.MAX_VALUE);
int idx = 0;

Connect now = new Connect(idx, 0);
pQueue.offer(now);

 

탐색과 출력

• 방문한 정점은 거리가 가장 짧은 정점이므로 방문처리를 하고, cost에 그 값을 더한다. 
• 0부터 N-1까지 섬들을 탐색하면서 방문하지 않은 배열이라면 현재 섬과 다음 섬(i)의 거리를 계산해서 큐에 넣는다.
• 이 때, 현재 섬이 가지고 있는 길이와 더하지 않고 지금 계산한 거리만을 넣는다. 어떤 섬이 마지막일지 모르기 때문에 cost에 각각 더하는 방식으로 계산을 편하게 하기 위함이다.
• 마지막으로 모두 더한 cost에 E를 곱해서 총 환경부담금을 계산한다. Math.round함수를 이용해 반올림한다. 

while (!pQueue.isEmpty()) {
   now = pQueue.poll();
   if (visited[idx = now.idx]) continue;
   visited[idx] = true;
   distance[idx] = now.length;
   cost+= distance[idx];

   for (int i = 0; i < N; i++) {
      if (visited[i]) continue;
      long length = (long) (Math.pow(Math.abs(island[idx][0] - island[i][0]),2) + Math.pow(Math.abs(island[idx][1] - island[i][1]),2));
      if (distance[i] > now.length+length) pQueue.offer(new Connect(i, length));
   }
}

//pQueue.clear(); //항상 비어있음
sb.append(Math.round(cost * E)).append("\n");

 

전체 코드

import java.io.*;
import java.util.*;

public class D4_1251_하나로 {
   public static void main(String[] args) throws Exception {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();
      StringTokenizer st;

      int T = Integer.parseInt(in.readLine());

      int N;
      int[][] island;
      long[] distance;
      boolean[] visited;
      double E, cost;

      PriorityQueue<Connect> pQueue = new PriorityQueue<>();

      for (int tc = 1; tc <= T; tc++) {
         sb.append("#").append(tc).append(" ");
         N = Integer.parseInt(in.readLine());
         island = new int[N][2];

         st = new StringTokenizer(in.readLine());
         for (int n = 0; n < N; n++) island[n][0] = Integer.parseInt(st.nextToken());

         st = new StringTokenizer(in.readLine());
         for (int n = 0; n < N; n++) island[n][1] = Integer.parseInt(st.nextToken());

         E = Double.parseDouble(in.readLine());
         cost = 0;

         visited = new boolean[N];
         distance = new long[N];
         Arrays.fill(distance, Long.MAX_VALUE);
         int idx = 0;

         Connect now = new Connect(idx, 0);
         pQueue.offer(now);

         while (!pQueue.isEmpty()) {
            now = pQueue.poll();
            if (visited[idx = now.idx]) continue;
            visited[idx] = true;
            distance[idx] = now.length;
            cost+= distance[idx];

            for (int i = 0; i < N; i++) {
               if (visited[i]) continue;
               long length = (long) (Math.pow(Math.abs(island[idx][0] - island[i][0]),2) + Math.pow(Math.abs(island[idx][1] - island[i][1]),2));
               if (distance[i] > now.length+length) pQueue.offer(new Connect(i, length));
            }
         }

         //pQueue.clear(); //항상 비어있음
         sb.append(Math.round(cost * E)).append("\n");
      }

      System.out.print(sb);
   }

   static class Connect implements Comparable<Connect> {
      int idx;
      long length;

      private Connect(int idx, long length) {
         this.idx = idx;
         this.length = length;
      }

      @Override
      public int compareTo(Connect o) {
         return Long.valueOf(this.length).compareTo(o.length);
      }
   }
}

---

3. 결과

두 점 사이의 거리 공식을 잘못써서 틀렸다.

두번째와 세번째의 차이는 String.format("%.0f",cost*E)와 Math.round(cost*E) 한 줄이다.

얼마나 차이가 나나 궁금해서 해봤는데 엄청나게 차이를 보이진 않았지만 그래도 메모리나 시간이나 Math.round가 더 유리하다.