[백준][JAVA] BOJ 1368 물대기

문제 읽기🤔

---

 

문제

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

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

입력

첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)를 의미한다.

출력

첫 줄에 모든 논에 물을 대는데 필요한 최소비용을 출력한다.

예제 입력 1

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

예제 출력 1

9

 

 

문제 풀이📝

---

MST 문제였다.

보자마자 프림 알고리즘 풀이가 떠올랐다!

처음에는 단순히 시작노드마다 프림 알고리즘을 돌아서 최솟값을 구하는 풀이를 생각했다.

당연히 시간초과를 뚜들겨 맞았다. N번 로직을 도는 거니까... 왜 그때는 생각을 못했을까?

 

풀이는 놀랍게도 단순하다.

이 문제의 특이한 점은 이미 물을 댄 논에서만 물을 가져올 수 있다는 조건이 있다는 것이다.

처음에는 모든 논이 물을 대지 않은 상태기 때문에, 무조건 한 번은 우물을 파는 결정을 해야 한다.

그렇기 때문에 우선순위 큐에 각 정점 스스로를 가리키는 간선들을 넣어둔 채로 프림 알고리즘 로직을 수행했다.

어차피 MST이기 때문에 모든 정점을 방문한 후에 자동 종료되며, 계산한 total값은 우리가 원하는 최솟값이 된다.

 

구현🛠️

---

package com.ssafy.baekjoon.random;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_1368 {

    static class Edge implements Comparable<Edge>{
        int vertex;
        int weight;

        Edge(int vertex, int cost){
            this.vertex = vertex;
            this.weight = cost;
        }

        @Override
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    static int N;
    static List<Edge>[] graph;
    static PriorityQueue<Edge> pq;

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

        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }

        pq = new PriorityQueue<>();
        // 우물을 파는 경우 -> 시작 노드 역할, pq에 넣어서 가장 작은 시작 노드를 꺼낼 것임
        for (int i = 0; i < N; i++) {
            int weight = Integer.parseInt(br.readLine());
            pq.offer(new Edge(i, weight));
        }

        for (int from = 0; from < N; from++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int to = 0; to < N; to++) {
                int weight = Integer.parseInt(st.nextToken());
                graph[from].add(new Edge(to, weight));
                graph[to].add(new Edge(from, weight));
            }
        }

        System.out.println(prim());
    }

    // prim 알고리즘
    static int prim() {
        boolean[] visited = new boolean[N];

        int total = 0;
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int vertex = edge.vertex;
            int weight = edge.weight;

            // 중복 방문 방지
            if (visited[vertex]) {
                continue;
            }

            visited[vertex] = true;
            total += weight;

            // 해당 노드와 연결된 간선들을 pq에 넣음
            for (Edge e : graph[vertex]) {
                if (!visited[e.vertex]){
                    pq.offer(e);
                }
            }
        }

        return total;
    }
}

 

 

실행결과✅

---