[백준] 1197번 - 최소 스패닝 트리

 

1197번: 최소 스패닝 트리

 

 

프로그래머스 섬 연결하기와 동일한 문제이다. 

[프로그래머스] 섬 연결하기

 

 

무방향 가중치 그래프에서 모든 정점을 연결하는 동시에 가중치 합의 최소를 구하는 '최소 신장 트리'를 구하는 문제이다. 

문제풀이에 사용할 수 있는 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 있고, 두 방법을 모두 사용하여 문제풀이를 해보겠다.

 

우선 최소 신장 트리를 구하는 두 알고리즘에 대한 설명은 아래와 같다.

최소 신장 트리(Minimum Spanning Tree)

 

 

 

 

 

크루스칼 알고리즘을 사용하는 경우 원리는 부모 노드가 같은 두 정점은 같은 트리에 포함된다는 성질을 이용한다.  그러기 위해서는 부모 노드를 저장하는 배열 parent[]가 필요하고 간선의 가중치 기준 오름차순 정렬을 해야한다. 그 다음 가중치가 가장 작은 간선부터 오름차순으로 진행한다. 

출발하는 from 정점과 도착하는 to 정점의 부모 노드가 서로 같다면 해당 간선은 고려하지 않는다. 반면 두 정점의 부모 노드가 서로 다르다면 해당 간선의 가중치를 최종 결과에 더해주고 두 정점의 부모 노드를 from 정점의 부모 노드로 같게 만들어 준다. 

 

여담으로 이전까지 객체 정렬에 람다 표현식을 주로 사용했었는데 Comparable 을 구현하는 방식을 연습겸 사용하였다. 

 

 

크루스칼 알고리즘을 사용한 전체 코드

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

public class Main {
    
    private static class Node implements Comparable<Node>{
        int from;
        int to;
        int weight;
        public Node (int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        
        @Override
        public int compareTo (Node node) {
            return this.weight - node.weight;
        }
    }
    
    
    static int V, E, parent[];
    
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] input = br.readLine().split(" ");
        V = Integer.parseInt(input[0]+1);
        E = Integer.parseInt(input[1]);
        
        parent = new int[V+1];
        Node[] costs = new Node[E];
        
        // 처음 시작 시 정점 i의 부모 노드는 자기 자신이다.
        for (int i=1; i<=V; i++) parent[i] = i;
        
        for (int i=0; i<E; i++) {
            input = br.readLine().split(" ");
            int from = Integer.parseInt(input[0]);
            int to = Integer.parseInt(input[1]);
            int weight = Integer.parseInt(input[2]);
            costs[i] = new Node(from, to, weight);
        }
        
        // 크루스칼 알고리즘을 사용하기 위해서는 가중치 기준 오름차순 정렬이 되어 있어야 한다.
        Arrays.sort(costs);
        
        int result = 0;
        
        // 가중치가 낮은 간선부터 탐색하므로 최소 가중치를 유지하면서 정점들으 연결할 수 있다.
        for (Node node : costs) {
            
            int from = node.from;
            int to = node.to;
            int weight = node.weight;
            
            int fromParent = findParent(from);
            int toParent = findParent(to);
            
            // from 과 to의 부모 노드가 같다면 두 정점은 이미 최소 가중치 상태로 연결되어 있으므로 pass
            if (fromParent == toParent) continue;
            
            result += weight;
            
            
            // to 정점의 부모를 from 정점의 부모와 동일하게 만들어서 이 다음에 to에 연결되는 다른 정점들도 
            // 현재의 from 정점과 연결되도록 만든다.
            parent[toParent] = fromParent;
        }
        
        
        System.out.println(result);
        
        br.close();
    }
    
    // 매개변수로 들어온 정점의 부모노드가 자기자신이 될 때까지 재귀호출한다. 
    static int findParent (int node) {
        if (parent[node] == node) return node;
        return findParent(parent[node]);
    }
}

 

 

 

프림 알고리즘은 우선순위 큐를 사용하여 구현한다. 낮은 가중치를 갖는 Node 객체가 높은 먼저 빠져나오는 우선순위 큐를 생성한다. 추가로 양방향 그래프의 두 정점간 관계를 저장하기 위한 List나 이중 배열이 필요한데 필자는 보통 list를 이용한다. 그 다음 출발할 정점을 큐에 넣어주는데 결과적으로 모든 정점이 연결되어야 하므로 출발 정점은 아무 거나 골라도 된다. 

그 다음 큐가 비어있지 않다면 아래의 과정을 반복한다.

 

i) 현재 큐에 들어있는 데이터 중 우선순위가 가장 높은(가중치가 가장 작은) 간선 정보를 꺼낸다.

ii)  해당 정점을 방문하지 않았다면 방문처리하고 출력할 결과에 해당 간선의 가중치를 더한다.

iii) 그 다음 현재 위치한 정점에서 이동할 수 있는 정점 중 아직 방문하지 않은 정점과의 간선 정보를 큐에 넣는다.

 

while 반복문의 매 시작에 큐에서 꺼내는 데이터는 언제나 가중치가 가장 작은 간선에 대한 정보이다. 따라서 최종적으로 최소 신장 트리를 형성하게 된다.

 

프림 알고리즘을 사용한 전체 코드

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

public class Main {
    
    private static class Node implements Comparable<Node> {
        
        int edge;
        int weight;
        public Node (int edge, int weight) {
            this.edge = edge;
            this.weight = weight;
        }
        
        @Override
        public int compareTo (Node o) {
            return this.weight - o.weight;
        }
    }
    
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Node> que = new PriorityQueue<>();
            
        String[] input = br.readLine().split(" ");
        int V = Integer.parseInt(input[0]+1);
        int E = Integer.parseInt(input[1]);
        
        List<Node>[] link = new ArrayList[V+1];
        Node[] costs = new Node[E];
        boolean[] visited = new boolean[V+1];
        
        for (int i=1; i<=V; i++) link[i] = new ArrayList<>();
        
        for (int i=0; i<E; i++) {
            input = br.readLine().split(" ");
            int from = Integer.parseInt(input[0]);
            int to = Integer.parseInt(input[1]);
            int weight = Integer.parseInt(input[2]);
            link[from].add(new Node(to, weight));
            link[to].add(new Node(from, weight));
        }
        
        
        int result = 0;
        
        que.offer(new Node(1, 0));
        
        while (!que.isEmpty()) {
            
            Node n = que.poll();
            
            // 이미 방문한 정점이라면 고려하지 않는다.
            if (visited[n.edge]) continue;
            
            int now = n.edge;
            int weight = n.weight;
            
            // 우선순위 큐에 의해 현 상태에서 연결할 수 있는 간선 중 가장 가중치가 작은 간선다. 
            visited[now] = true;
            result += weight;
            
            for (Node next : link[now]) {
            	// 다음으로 이동할 수 있는 정점이면서 아직 방문하지 않은 정점이면 큐에 넣는다.
                if (!visited[next.edge]) {
                    que.offer(next);
                }
            }
            
        }
        
        
        System.out.println(result);
        
        br.close();
    }
}