백준 1368 (물대기) - java

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

1368번: 물대기

 

문제

선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.

 

유형 : MST

 

접근 방식

• 직접 물을 주는 것과 간선을 통해 물을 흘려 보내는 것 2가지를 고려해야 하는 문제이다.
  • 여기서 핵심은 물을 직접 주는 과정은 적어도 1번 이상 있어야 한다는 것이다.
• 그렇다면 직접 물을 주는 것의 가장 작은 값 1개로 풀어야 할까?
  • 해당 지점의 간선 값이 크면 ? -> 완벽한 풀이가 될까?
• 2가지를 한번에 고려하는 것은 결국 해당 문제를 쉽게 해결할 수 없다.
• 하지만 간단하게 생각해보자 -> 직접 물을 주는 것을 0 번째 지점이라고 한다면?
  • 가상의 0 번째 지점을 만들고 MST 만드는 것이다 !!!! 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int[][] d;

    static int[] s;

    static int[] root;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        d = new int[n+1][n+1];
        s = new int[n+1];
        root = new int[n+1];

        for(int i=1;i<=n;i++){
            root[i] = i;
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        int total = 0;

        for(int i=1;i<=n;i++){
            int cur = Integer.parseInt(bf.readLine());
            s[i] = cur;

            pq.add(new Node(0,i,s[i]));
        }

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(bf.readLine(), " ");

            for(int j=1;j<=n;j++){
                d[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                pq.add(new Node(i,j,d[i][j]));
            }
        }



        int count = 0;

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(find(cur.v1) != find(cur.v2)){
                union(cur.v1,cur.v2);
                count += 1;
                total += cur.c;
            }

            if(count == n)
                break;
        }

        System.out.println(total);

        bf.close();
    }

    static int find(int x){
        if(x == root[x])
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y){
            root[y] = x;
        }else{
            root[x] = y;
        }
    }
}
class Node{
    int v1; // 정점 1
    int v2; // 정점 2
    int c; // 간선 값

    Node(int v1,int v2,int c){
        this.v1 = v1;
        this.v2 = v2;
        this.c = c;
    }
}