[BOJ1368] 물대기 (프림 알고리즘, 최소 신장 트리, 그리디)

 

 

---

문제 링크

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

1368번: 물대기

 

문제 풀이 

문제를 접근할 때 우물을 무조건 하나 파야 한다고 생각해서

제일 적은 비용이 드는 우물을 기준으로 구했으나 '틀렸습니다' 만 나왔다

 

기술 블로그를 찾아본 결과, 우물을 하나 파는 행위를 간선(Edge) 정보로 추가해서 풀이해야 했다.

- 임의 노드 0번에 {i번 논, 논을 파는 비용} 으로 정의해서 컬렉션에 담는다

- 그리고 0번 노드부터 시작하여 결과값을 구하니 통과가 되었다

 

논을 파는 행위를 간선으로 정의해야 한다니

 

0 -> 4 -- 비용 3 (최초 4번 논을 판다)
4 -> 1 --  비용 2
1 -> 2 --  비용 2
1 -> 3 --  비용 2

총 비용:  9

 

프림 알고리즘을 사용했고, 비용 기준으로 오름차순 정렬 
시간 복잡도 : O(ElogV)

 

제출 코드

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

public class Main {
    static int N;

    static List<Edge>[] adj;

    static class Edge implements Comparable<Edge> {
        int idx;
        int cost;

        public Edge(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge edge) {
            return cost - edge.cost;
        }
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        // 논을 파는 비용
        int[] w = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            w[i] = Integer.parseInt(br.readLine());
        }

        adj = new ArrayList[N + 1]; // 0번 노드까지 초기화
        for(int i = 0; i <= N; i++) adj[i] = new ArrayList<>();

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

                if(i != j) adj[i].add(new Edge(j, cost));
                else adj[0].add(new Edge(i, w[i])); // 논을 파는 행위를 간선 정보로 저장
            }
        }
    }

    static int prime(int start) {
        Queue<Edge> que = new PriorityQueue<>();
        que.add(new Edge(start, 0));

        boolean[] visit = new boolean[N + 1];

        int result = 0;
        while(!que.isEmpty()) {
            Edge cur = que.poll();

            if(visit[cur.idx]) continue;

            visit[cur.idx] = true;
            result += cur.cost;

            for(Edge next : adj[cur.idx]) {
                if(visit[next.idx]) continue;

                que.add(next);
            }
        }

        return result;
    }

    static void pro() {
        System.out.println(prime(0));
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}