[백준]10021. Watering the Fields

📄 링크

Watering the Fields

---

💡 문제 분석

최대 2000개의 정점을 가진 그래프의 MST를 구하는 문제입니다
정점들 사이의 거리를 구하고 입력에 주어진 C값으로 간선의 수를 제한하고 있지만, 상당히 많은 간선이 생길 것 같아 프림 알고리즘을 사용하기로 했습니다.

프림 알고리즘

1. 모든 정점들에 굉장히 큰 값을 주고 시작합니다
2. 임의로 시작 정점을 골라 연결되어 있는 정점들의 가중치를 갱신합니다
3. 정점들 중 가장 가중치가 작은 정점을 골라 이를 반복합니다.(우선순위 큐를 사용할 수도 있습니다)
4. 모든 정점을 갱신했다면 종료

→ 이 문제에서는 그래프가 연결되어 있지 않은 경우가 존재하기 때문에 모든 정점을 검사하여 한 번도 갱신되지 않은 정점이 있다면 분리되어 있다고 판단하여 -1을 출력하도록 하였습니다.

---

⌨️ 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class _10211_Watering_the_Fields {
    static class Pair {
        int first, second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
    static int V, C;
    static int[] x, y;
    static ArrayList<Pair>[] adj;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        C = sc.nextInt();
        adj = new ArrayList[V];
        x = new int[V];
        y = new int[V];
        for(int i = 0; i < V; i++)
            adj[i] = new ArrayList<>();
        for(int i = 0; i < V; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }

        for(int i = 0; i < V - 1; i++) {
            for(int j = i + 1; j < V; j++) {
                int d = (int) (Math.pow(x[i] - x[j], 2) + Math.pow(y[i] - y[j], 2));
                if(C <= d) {
                    adj[i].add(new Pair(j, d));
                    adj[j].add(new Pair(i, d));
                }
            }
        }
        System.out.println(prim());
    }

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

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

---

📋 회고

• MST, 프림, 크루스칼
• 구현 연습