[Java] 1197번 : 최소 스패닝 트리

[peppermintt0504]

문제 풀이

해당 문제는 최소 신장 트리(MST)를 구하는 문제로 최소 신장 트리를 구하는 방법은 대표적으로 두가지 방법이 있다.

Prim 알고리즘 -> 2023.08.09 - [algorithm/theory] - Prim 알고리즘 Kruskal 알고리즘 -> 2023.08.10 - [algorithm/theory] - Kruskal 알고리즘 해당 알고리즘 설명은 이전에 포스팅한 글을 참고하면 될 것 같다.

최소 신장 트리 관련 문제는 처음 풀기 때문에 두 가지 방법 모두 사용하여 풀어보자.

1. Prim 알고리즘

프림 알고리즘 동작 과정은 아래와 같다.

1. 임의의 간선을 선택한다.
2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택한다.
3. 모든 정점에 대하여 2번의 과정을 반복한다.

4. 이를 적용하여 풀면 쉽게 답이 나온다.

   import java.util.*;
   import java.io.*;
   public class Main {
   public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
   public static StringTokenizer st;
   
   public static int V;
   public static int E;
   public static Map<Integer,ArrayList<Node>> nodes = new HashMap<>();
   public static PriorityQueue<Node> pq = new PriorityQueue<>();
   
   public static class Node implements Comparable<Node>{
   
       int to;
       int val;
   
       public Node() {}
   
       public Node(int to,int val) {
           this.to = to;
           this.val = val;
       }
       @Override
       public int compareTo(Node o) {
           return (this.val - o.val);
       }
   
   }
   
   public static void main(String[] args) throws IOException{
       st = new StringTokenizer(br.readLine());
   
       V = Integer.parseInt(st.nextToken());
       E = Integer.parseInt(st.nextToken());
   
       while(E --> 0) {
           st = new StringTokenizer(br.readLine());
           int n1 = Integer.parseInt(st.nextToken());
           int n2 = Integer.parseInt(st.nextToken());
           int val = Integer.parseInt(st.nextToken());
   
           if(!nodes.containsKey(n1)) 
               nodes.put(n1, new ArrayList<>());
           nodes.get(n1).add(new Node(n2,val));
   
           if(!nodes.containsKey(n2)) 
               nodes.put(n2, new ArrayList<>());
           nodes.get(n2).add(new Node(n1,val));
   
       }
   
       boolean[] visited = new boolean[V+1];
       int answer = 0;
   
       pq.add(new Node(1,0));
   
       while(!pq.isEmpty()) {
           Node cur = pq.poll();
   
           if(visited[cur.to]) continue;
           visited[cur.to] = true;
           answer+=cur.val;
   
           for(Node n : nodes.get(cur.to)) {
               if(!visited[n.to])
                   pq.add(n);
           }
       }
       System.out.println(answer);
   }
   }

2. Kruskal 알고리즘

크루스칼 알고리즘 동작은 아래와 같다.

1. 간선을 오름차순으로 선택한다.
2. 이 때 해당 간선을 추가하였을 때 노드가 순환한다면 해당 간선을 추가하지 않는다.

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

////Kruskal 알고리즘
public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StringTokenizer st;
    public static int INF = 100_000_000;
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {-1,0,1,0};

    public static int V;
    public static int E;
    public static int[] parent;
    public static Map<Integer,ArrayList<Node>> nodes = new HashMap<>();
    public static PriorityQueue<Node> pq = new PriorityQueue<>();

    public static class Node implements Comparable<Node>{
        int from;
        int to;
        int val;

        public Node() {}

        public Node(int from,int to,int val) {
            this.from = from;
            this.to = to;
            this.val = val;
        }
        @Override
        public int compareTo(Node o) {
            return (this.val - o.val);
        }

    }

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

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        parent = new int[V+1];
        for(int i=1; i <= V; i++) {
            parent[i] = i;
        }

        while(E --> 0) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());

            pq.add(new Node(n1,n2,val));
        }

        boolean[] visited = new boolean[V+1];
        int answer = 0;

        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            int to = find(cur.to);
            int from = find(cur.from);

            if(!isSameParent(to,from)) {
                answer += cur.val;
                union(cur.to, cur.from);
            }

        }
        System.out.println(answer);
    }

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

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x!= y) {
            parent[y] =x;
        }
    }

    public static boolean isSameParent(int x, int y ) {
        x = find(x);
        y = find(y);
        if(x==y) return true;
        else return false;
    }
}