BOJ) 최소 스패닝 트리 (1197 번)

최소 스패닝 트리

1197번: 최소 스패닝 트리

 

최소 스패닝 트리

 

최소 신장 트리라고도 하며, Minimum Spanning Tree(MST) 로 많이 들어 봤을 것이다.

MST는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 가중치의 합이 최소가 되는 트리이다.

즉, 최소 가중치를 가지며 그래프의 모든 정점을 연결하는 방법이다.

이 때, cycle이 생겨서는 안된다.

 

이 문제는 Prim과 Kruskal 알고리즘 두 개로 풀어봤다.

 

Kruskal

 

먼저, Kruskal은 Find-Union이라는 이름으로도 많이 들어봤을 것이다.

가중치에 따라 오름차순으로 우선순위 큐에 edge의 정보를 저장한 다음, find-union을 통해 정점을 연결해나가는 방법이다.

find - unioin은 다른 게시물에서도 많이 언급했으므로, 자세한 설명은 생략한다.

 

 

Prim

 

Prim은 Kruskal과 마찬가지로 우선순위 큐를 사용한다.

하지만, Kruskal처럼 모든 edge정보를 우선순위 큐에 저장한 다음 진행하는 것이 아니라, 엣지의 정보는 따로 가지고 있고 임의의 노드에서 연결을 시작하는 것이다.

 

1) 임의의 노드를 우선순위 큐에 입력한다.

2) 큐에서 추출한 노드를 방문한 적이 없다면, 가중치를 더하고 방문 표시를 한다.

3) 2)의 노드와 연결된 노드가 있는지 탐색 && 연결된 노드에 방문한 적이 없다면 큐에 입력한다.

4) 모든 노드를 이을때 까지 반복한다.

 

Greedy하게 BST를 진행하는 알고리즘이다.

 

 

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 MinSpanningTree_1197{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        ArrayList<Node>[] edgeList = new ArrayList[v+1];
        for(int i=0; i<=v; i++) {
            edgeList[i] = new ArrayList<>();
        }

        while(e >0) {
            st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            edgeList[left].add(new Node(right, weight));
            edgeList[right].add(new Node(left,weight));

            e--;
        }

        solution(v, edgeList);
    }

    private static void solution(int v, ArrayList<Node>[] edgeList) {
        int answer =0, remain =v;
        boolean[] visit = new boolean[v+1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(1,0));

        while(!pq.isEmpty()) {
            Node now = pq.poll();
            if(!visit[now.vertex]) {
                visit[now.vertex] = true;
                answer += now.weight;
                remain--;
                ArrayList<Node> nextNodes = edgeList[now.vertex];
                for(Node next : nextNodes) {
                    if(!visit[next.vertex]) {
                        pq.offer(next);
                    }
                }
            }
            if(remain == 0) {
                break;
            }
        }
        System.out.println(answer);
    }

    private static class Node implements Comparable<Node> {
        int vertex, weight;

        public Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node tree) {
            return this.weight - tree.weight;
        }
    }
}

 

 

Kruskal 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class MinSpanningTreeKruskal_1197 {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        PriorityQueue<Edge> pq = new PriorityQueue<>();

        while(e >0) {
            st = new StringTokenizer(br.readLine());
            pq.offer(new Edge(Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken())));
            e--;
        }

        solution(v, pq);
    }

    private static void solution(int v, PriorityQueue<Edge> pq) {
        int answer =0, remain =v;
        initParent(v+1);

        while(!pq.isEmpty()) {
            Edge edge = pq.poll();
            if(find(edge.left) != find(edge.right)) {
                answer += edge.weight;
                union(edge.left, edge.right);
                if(--remain ==0) {
                    break;
                }
            }
        }
        System.out.println(answer);
    }

    private static void initParent(int n) {
        parent = new int[n+1];
        for(int i=1; i<=n; i++) {
            parent[i] = i;
        }
    }

    private static int find(int index) {
        if(index == parent[index]) {
            return index;
        }
        return parent[index] = find(parent[index]);
    }

    private static void union(int left, int right) {
        left = find(left);
        right = find(right);
        if(left != right) {
            parent[right] = left;
        }
    }

    private static class Edge implements Comparable<Edge>{
        int left, right, weight;

        public Edge(int left, int right, int weight) {
            this.left = left;
            this.right = right;
            this.weight = weight;
        }

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