[백준(Python/Java)] 6497_전력난

6497번: 전력난

 

이 문제는 도시의 모든 집을 연결할 수 있는 최소한의 간선(길)만을 선택하는 문제로, 최소 스패닝 트리(Minimum Spanning Tree, MST)를 이용해 풀 수 있습니다.

 

MST를 구현하는 방법에는 우선순위 큐를 이용하는 방법, 크루스칼 알고리즘을 이용하는 방법과 프림 알고리즘을 이용하는 방법이 있는데요. 이 문제에서는 MST에 보편적으로 쓰이는 크루스칼 알고리즘을 이용해 해결했습니다.

 

개별 간선(Edge)은 해당 길의 비용과 이어진 두 마을(정점)의 정보를 가지고 있는 클래스라고 정의합니다. 파이썬에서는 튜플 형태로 만들면 되고, 자바에서는 클래스로 정의하면 되겠죠? 그러면 Edges라는 모든 간선 정보를 저장하는 리스트를 생성할 수 있습니다. 그리고 이를 cost에 대한 오름차순으로 정렬하면 가장 비용이 적게 드는 간선부터 선택할 수 있게 됩니다.

 

그리고 모든 Edge를 순회하면서 해당 Edge를 선택하는 과정에서 싸이클이 생기는지 확인해주면 되는데요. 싸이클이 생기는 지 확인하기 위해서는 해당 간선으로 이어진 두 노드의 부모가 같은지를 확인해주면 됩니다. A, B, C라는 세 노드가 존재할 때, B와 C의 부모 노드가 A라는 것은 A-B, A-C가 이어져 있다는 것을 말하므로, 이 때 B-C를 연결하는 것은 불필요한 싸이클을 형성하는 것이죠.

 

이 과정을 모든 노드에 반복해주면서 싸이클이 생기지 않는 노드를 선택해주면, 위에서 Edges들을 비용에 대해 오름차순 정렬했기 때문에 최소 비용만을 가지고 모든 정점을 연결할 수 있는 MST가 만들어집니다.

 

풀이는 아래와 같습니다.

 

[풀이 - 파이썬]

import sys
input = sys.stdin.readline


def getParent(parent, node):
    if parent[node] == node:
        return node
    return getParent(parent, parent[node])

def unionParent(parent, x, y):

    parentOfX = getParent(parent, x)
    parentOfY = getParent(parent, y)
    if parentOfX > parentOfY:
        parent[parentOfX] = parentOfY
    else:
        parent[parentOfY] = parentOfX


def findMST():
    result = 0
    # 각 노드의 Parent 노드 정보 초기화 - 자기 자신
    parent = [i for i in range(m)]

    # 가장 적은 비용이 드는 간선 순으로 정렬
    edges.sort()

    for edge in edges:
        cost, x, y = edge
        
        # 싸이클이 없는 경우에 해당 간선 선택
        if getParent(parent,x) != getParent(parent, y):
            unionParent(parent, x, y)
            result += cost
    return result

while True:
    m, n = map(int, input().split())
    if m == 0 and n == 0:
        break

    edges = [] # 모든 간선 정보를 저장하는 리스트
    original_cost = 0 # 모든 길에 가로등이 있을 때 비용
    for _ in range(n):
        x, y, cost = map(int, input().split())
        edges.append((cost, x, y))
        original_cost += cost

    # 모든 집을 연결하는 최소 스패닝 트리 비용을 구한다.
    min_cost = findMST()
    
    saved_cost = original_cost - min_cost
    print(saved_cost)

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class B_6497 {
    static int n, m;
    static List<Edge> edges;

    public static int getParent(int[] parent, int node){
        if(parent[node] == node) return node;
        return getParent(parent, parent[node]);
    }

    public static void unionParent(int[] parent, int x, int y){
        int parentOfX = getParent(parent, x);
        int parentOfY = getParent(parent, y);
        if(parentOfX > parentOfY) parent[parentOfX] = parentOfY;
        else parent[parentOfY] = parentOfX;
    }
    public static int findMST(){
        int result = 0;

        // 각 노드의 Parent 노드 초기화
        int[] parent = new int[m];
        for(int i = 0; i < m; i++)
            parent[i] = i;

        // 가장 적은 비용이 드는 간선 순으로 정렬
        Collections.sort(edges);

        for(Edge edge : edges){
            int cost = edge.cost;
            int x = edge.x;
            int y =  edge.y;

            // 싸이클이 없는 경우에 해당 간선 선택
            if(getParent(parent, x) != getParent(parent, y)){
                unionParent(parent, x, y);
                result += cost;
            }
        }
        return result;
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            if(m == 0 && n == 0) break;

            edges = new ArrayList<>(); // 모든 간선 정보를 저장하는 리스트
            int original_cost = 0;

            for(int i = 0; i < n ; i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());
                edges.add(new Edge(cost, x, y));
                original_cost += cost;
            }

            // 모든 집을 연결하는 최소 스패닝 트리 비용을 구한다.
            int min_cost = findMST();
            System.out.println(original_cost - min_cost);
        }
    }

    static class Edge implements Comparable<Edge>{
        int cost, x, y;

        Edge(int cost, int x, int y){
            this.cost = cost;
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Edge other){
            return this.cost - other.cost;
        }
    }
}