[BOJ] 16398.행성 연결(MST, kruskal, prim).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이 문제도 마찬가지로

MST 기본 문제이다.

친절하게 입력으로 모든 간선의 가중치가 주어진다.

#. Code_Kruskal

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ16398_kruskal {
 
    static int N, parents[];
    static PriorityQueue<Edge> pq;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        parents = new int[N];
        pq = new PriorityQueue<>();
        // 행정 정보
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < N; j++) {
                int weight = Integer.parseInt(st.nextToken());
                if(i < j) pq.add(new Edge(i, j, weight));
            }
        }
 
        System.out.println(prim());
    }
 
    private static long prim() {
        
        long res = 0;
        int cnt = 0;
        
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
        
        while(!pq.isEmpty()) {
            Edge now = pq.poll();
            if(union(now)) {
                res += now.w;
                if(++cnt == N - 1) return res;
            }
        }
        
        return res;
    }
 
    private static boolean union(Edge now) {
        
        int aRoot = find(now.from);
        int bRoot = find(now.to);
        
        if(aRoot == bRoot) return false;
        
        parents[bRoot] = aRoot;
        return true;
        
    }
 
    private static int find(int n) {
        
        if(n == parents[n]) return n;
        return parents[n] = find(parents[n]);
        
    }
 
    static class Edge implements Comparable<Edge> {
        int from, to, w;
 
        public Edge(int from, int to, int w) {
            this.from = from;
            this.to = to;
            this.w = w;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.w, o.w);
        }
        
    }
}
 

#. Code_Prim

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ16398 {
 
    static int N;
    static ArrayList<Node> adj[];
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        adj = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adj[i] = new ArrayList<>();
        }
        // 행정 정보
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < N; j++) {
                int weight = Integer.parseInt(st.nextToken());
                if(i == j) continue;
                adj[i].add(new Node(j, weight));
            }
        }
 
        System.out.println(prim());
    }
 
    private static long prim() {
        
        long res = 0;
        int cnt = 0;
        boolean visited[] = new boolean[N];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 0번 행성부터 출발
        pq.add(new Node(0, 0));
        
        while(!pq.isEmpty()) {
            Node now = pq.poll();
            // 이미 방문한 행성
            if(visited[now.to]) continue;
            
            res += now.w;
            visited[now.to] = true;
            if(++cnt == N) return res;
            
            for (Node next : adj[now.to]) {
                if(visited[next.to]) continue;
                pq.add(next);
            }
        }
        
        return res;
    }
 
    
    static class Node implements Comparable<Node> {
        int to, w;
 
        public Node(int to, int w) {
            this.to = to;
            this.w = w;
        }
 
        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.w, o.w);
        }
        
    }
}