📙[Algo] 24.05.09 알고리즘

알고리즘 문제) BOJ 1368. 물대기

• 링크 : https://www.acmicpc.net/problem/1368

문제 요약

• N개의 논에 물을 대려고 한다.
• 물을 대는 방법에는 두 가지가 존재
  1. 직접 논에 우물을 파는 것
  2. 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 것
• 각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때, 논에 물을 대는 최소 비용 찾기

시간 제한

• 2초

입력

• 첫째 줄 : 논의 수N
  • 1 ≤ N ≤ 300
• 다음 N개의 줄에 i번째 논에 우물을 팔 때 드는 비용 Wi가 순서대로 주어짐
  • 1 ≤ Wi ≤ 10만
• 다음 N개의 줄에 각 줄에 N개의 수가 들어오는데, i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j를 의미
  • 1 ≤ Pi ≤ 10만

출력

• 모든 논에 물을 대는데 필요한 최소 비용 출력

접근법

• 그냥 자기 자신을 파는데 드는 비용은 가상 노드 0번을 만들어서 해당 노드로의 간선 비용으로 가정한다.
• 그리고 나서 MST 로 푸는 문제였다.

코드

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

public class Main {
    static int N;
    static int[] cost = new int[310];
    static int[] parent = new int[310];
    static boolean[] isWater = new boolean[310];
    static ArrayList<int[]> graph = new ArrayList<>();

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

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

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        // 우물파는 비용이 가장 적은 우물 찾으며 비용 입력 받기
        for (int i = 1; i <= N; i++) {
            cost[i] = Integer.parseInt(br.readLine());
        }

        graph = new ArrayList<>();

        int c;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                c = Integer.parseInt(st.nextToken());

                if (i == j) {
                    graph.add(new int[]{i, 0, cost[j]});
                    graph.add(new int[]{0, i, cost[j]});
                } else {
                    graph.add(new int[]{i, j, c});
                }
            }
        }

        // 비용 기준 오름차순 정렬
        Collections.sort(graph, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        // 부모 배열 초기화(자기 자신)
        for (int i = 0; i < 310; i++) {
            parent[i] = i;
        }

        // 크루스칼 알고리즘
        int v1, v2;
        int answer = 0;
        for (int i = 0; i < graph.size(); i++) {
            v1 = graph.get(i)[0];
            v2 = graph.get(i)[1];
            c = graph.get(i)[2];

            if (find(v1) == find(v2)) continue;

            union(v1, v2);
            answer += c;
        }

        System.out.println(answer);

        br.close();
    }
}