백준 10021번: Watering the Fields (Java)

접근

https://www.acmicpc.net/problem/10021

10021번: Watering the Fields

최소 신장 트리(MST, Minimum Spanning Tree) 문제였다. 모든 노드들이 연결되어 있는 상태가 되기 위한 최소의 간선 갯수는 N - 1 개이다. 이 문제에서는 두 노드 사이에 파이프를 건설하는 비용이 가중치로 주어지면서, 그 건설 비용이 C 이하라면 건설이 되지 않는 조건이 추가되어 있다.

최소 신장 트리를 해결하는 알고리즘에는 kruskal 알고리즘과 prim 알고리즘이 있는데, 간선의 수가 작은 희소 그래프(sparse graph) 일 때는 kruskal 알고리즘이 유리하고, 간선의 수가 많은 밀집 그래프(dense graph) 일 경우 prim 알고리즘이 유리하다. 이 문제에서 최소 파이프 건설 비용이 C로 주어져 있기는 하지만 모든 노드가 서로 연결될 수 있는 가능성이 있기 때문에 prim 알고리즘을 이용해 풀기로 한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

  static class Pair {

    int first, second;

    Pair(int first, int second) {
      this.first = first;
      this.second = second;
    }
  }

  static int costCalculation(int a, int b) {
    int ans = (X[a] - X[b]) * (X[a] - X[b]) + (Y[a] - Y[b]) * (Y[a] - Y[b]);
    return ans;
  }

  static int N, C;
  static int[] X, Y;
  static ArrayList<Pair>[] adj;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] input = br.readLine().split(" ");
    N = Integer.parseInt(input[0]);
    C = Integer.parseInt(input[1]);

    adj = new ArrayList[N];
    X = new int[N];
    Y = new int[N];
    for (int i = 0; i < N; i++) {
      adj[i] = new ArrayList<>();
    }
    for (int i = 0; i < N; i++) {
      input = br.readLine().split(" ");
      X[i] = Integer.parseInt(input[0]);
      Y[i] = Integer.parseInt(input[1]);
    }

    for (int i = 0; i < N - 1; i++) {
      for (int j = i + 1; j < N; j++) {
        int d = costCalculation(i, j);
        if (C <= d) {
          adj[i].add(new Pair(j, d));
          adj[j].add(new Pair(i, d));
        }
      }
    }
    br.close();

    boolean[] added = new boolean[N];
    int[] minWeight = new int[N];
    Arrays.fill(minWeight, Integer.MAX_VALUE);
    int ret = 0;
    minWeight[0] = 0;
    for (int iter = 0; iter < N; iter++) {
      int u = -1;
      for (int n = 0; n < N; n++) {
        if (!added[n] && (u == -1 || minWeight[u] > minWeight[n])) {
          u = n;
        }
      }
      ret += minWeight[u];
      added[u] = true;

      for (int i = 0; i < adj[u].size(); i++) {
        int n = adj[u].get(i).first, weight = adj[u].get(i).second;
        if (!added[n] && minWeight[n] > weight) {
          minWeight[n] = weight;
        }
      }
    }
    for (int n : minWeight) {
      if (n == Integer.MAX_VALUE) {
        ret = -1;
      }
    }
    System.out.println(ret);
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!