10021 - Watering the Fields (Java)

박세건·2025년 2월 11일

백준

알고리즘 문제 해결

목록 보기

4/50

📌 문제 설명

백준 10021번 - Watering the Fields

N개의 농장이 2차원 좌표로 주어지고, 각 농장을 연결하는 비용이 유클리드 거리의 제곱((x1 - x2)^2 + (y1 - y2)^2)으로 결정됨.
특정 비용 C보다 작은 간선은 선택할 수 없음.
최소 비용으로 모든 농장을 연결하는 문제이므로 최소 신장 트리(MST, Minimum Spanning Tree) 알고리즘을 적용해야 함.
모든 농장을 연결할 수 없는 경우 -1을 출력.

💡 접근 방식

🔹 1️⃣ 최소 신장 트리(MST) 알고리즘 적용

그래프 내 모든 정점을 연결하는 최소 비용 트리를 구해야 하므로, MST(Minimum Spanning Tree) 문제임.
MST 문제를 해결하는 대표적인 두 가지 알고리즘이 있음.

알고리즘	시간복잡도	특징
크루스칼 (Kruskal)	`O(E log E)`	간선이 적을 때 유리 (정렬 + 유니온 파인드)
프림 (Prim)	`O(E log V)`	간선이 많을 때 유리 (우선순위 큐)

문제의 특성상 간선이 많다고 판단하여 프림 알고리즘을 적용!
- 최대 N은 1000, 두 농장 사이의 모든 간선을 만들 수 있으므로 E = O(N^2) 가능.
- 크루스칼을 사용하면 간선을 정렬하는 데 O(E log E), 즉 O(N^2 log N^2) ≈ O(N^2 log N)이 걸림.
- 프림 알고리즘을 사용하면 O(E log V) = O(N^2 log N)이므로 더 적합!.

❌ 초기 코드의 문제점

방문 처리를 PQ에 추가할 때 수행 → 잘못된 방문 처리로 인해 오답 발생.

✅ 일반적인 BFS의 방문 처리 방식

for (int next : connInfo[cur]) {
    if (visited[next]) continue; // 방문한 적 있으면 건너뜀
    visited[next] = true; // 방문 처리
    queue.add(next);
}

BFS는 탐색할 때(Queue에 넣을 때) 방문 처리를 수행.

❌ 초기 코드의 방문 처리 문제

for (int i = 0; i < N; i++) {
    if (connMap[num][i] < C) continue;
    if (visited[i]) continue; // ❌ 방문 처리 위치가 잘못됨
    pq.add(new int[]{i, connMap[num][i]});
    visited[i] = true; // ❌ 큐에 넣을 때 방문 처리 → 잘못된 방식
}

프림 알고리즘에서는 PQ에서 꺼낼 때 방문 처리를 해야 함!
이유: 우선순위 큐에 더 작은 비용의 간선이 나중에 들어올 수도 있기 때문.

✅ 정답 코드 (프림 알고리즘)

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;
    private static int N, C;
    private static int[][] nodes;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        setting();
        System.out.println(prim());
    }

    private static long prim() {
        long answer = 0;
        int edgeCount = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        visited = new boolean[N];

        // 1. 초기 노드(0)부터 시작
        pq.add(new int[]{0, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int num = cur[0];
            int val = cur[1];

            // 2. 이미 방문한 노드라면 스킵
            if (visited[num]) continue;

            // 3. 방문 처리 및 비용 추가
            visited[num] = true;
            answer += val;
            edgeCount++;

            // 4. 현재 노드와 연결된 간선 추가
            for (int i = 0; i < N; i++) {
                if (!visited[i]) {
                    int connValue = getConnValue(nodes[num][0], nodes[num][1], nodes[i][0], nodes[i][1]);
                    if (connValue >= C) {
                        pq.add(new int[]{i, connValue});
                    }
                }
            }
        }

        // 5. 모든 노드가 연결되지 않았다면 -1 반환
        return (edgeCount == N) ? answer : -1;
    }

    private static void setting() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        nodes = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            nodes[i][0] = Integer.parseInt(st.nextToken());
            nodes[i][1] = Integer.parseInt(st.nextToken());
        }
    }

    private static int getConnValue(int x1, int y1, int x2, int y2) {
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    }
}

🔍 코드 분석

함수	역할
`setting()`	입력 처리 및 농장 위치 저장
`prim()`	프림 알고리즘을 사용하여 MST 구성
`getConnValue(x1, y1, x2, y2)`	두 농장의 거리 제곱 계산

🚀 최적화 가능성

✅ 프림 알고리즘을 더욱 최적화하는 방법

우선순위 큐를 int[] 대신 class로 변경

int[] 배열 대신 class Edge를 사용하면 코드 가독성이 향상됨.

class Edge implements Comparable<Edge> {
    int node, weight;
    Edge(int node, int weight) { this.node = node; this.weight = weight; }
    @Override
    public int compareTo(Edge o) { return this.weight - o.weight; }
}

배열 대신 List<List<Edge>> graph 사용
- 현재 connMap을 2차원 배열로 저장했지만, 메모리 낭비가 발생함.
- 리스트로 변환하면 필요할 때만 간선 정보 저장할 수 있어 메모리 절약 가능.
```
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < N; i++) graph.add(new ArrayList<>());
graph.get(i).add(new Edge(j, cost));
```
프림 알고리즘의 시간 복잡도 최적화
- 현재 O(N^2 log N), E ≈ O(N^2)이라서 크루스칼보다 효율적.
- 만약 E가 훨씬 적다면 크루스칼 알고리즘이 더 유리할 수도 있음.