[백준]1922: 네트워크 연결

[백준]1922: 네트워크 연결

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

풀이

어제 MST를 공부한 기념으로 MST문제를 풀어보았다!

 

MST는 prim알고리즘과 kruskal알고리즘으로 풀 수 있다. 두 알고리즘을 모두 사용하여 문제를 풀어보았다. 

이번 문제는 변형 1도 없이 MST알고리즘만 쓰면 답이 나온다!

 

코드

• prim algorithmn

import java.util.*;
 
public class Main {    
    
    static boolean[] visited;
    static int min = 0;
    static ArrayList<Node>[] list;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int m = scan.nextInt();
        
        list = new ArrayList[n + 1];
        for(int i = 1; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0;  i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int cost = scan.nextInt();
            list[s].add(new Node(e, cost));
            list[e].add(new Node(s, cost));
        }
        
        visited = new boolean[n + 1];
        prim();
        System.out.println(min);
    }
    
    public static void prim() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(1, 0));
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(visited[current.x] == false) visited[current.x] = true;
            else continue;
            
            min += current.cost;
            for(int i = 0; i < list[current.x].size(); i++) {
                Node next = list[current.x].get(i);
                q.offer(next);
            }
        }
    }
    
    public static class Node implements Comparable<Node>{
        int x;
        int cost;
        
        public Node(int x, int cost) {
            this.x = x;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}

 

• kruskal algorithmn

import java.util.*;
 
public class Main {    
    
    static boolean[] visited;
    static int min = 0;
    static int[] parent;
    static PriorityQueue<Node> q;
    static int n, m;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        
        q = new PriorityQueue<>();
        for(int i = 0;  i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int cost = scan.nextInt();
            q.add(new Node(s, e, cost));
        }
        
        parent = new int[n + 1];
        kruskal();    
        System.out.println(min);
    }
    
    public static void kruskal() {
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            int p1 = find(node.s);
            int p2 = find(node.e);
            
            if(p1 != p2) {
                union(p1, p2);
                min += node.cost;
            }
        }
    }
    
    public static void union(int a, int b) {
        parent[a] = b;
    }
    
    public static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
    
    public static class Node implements Comparable<Node>{
        int s;
        int e;
        int cost;
        
        public Node(int s, int e, int cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}