[BOJ 16398] 행성 연결 - JAVA, Gold4

https://www.acmicpc.net/problem/16398

16398번: 행성 연결

사용한 알고리즘 : MST(최소 스패닝 트리)

 

풀이 전략

전형적인 최소 스패닝 트리를 사용한 문제이다.

그래프의 모든 간선들 중에서 비용이 가장 적은 간선을 하나씩 더해간다.

단, 더해가는 과정에서 싸이클이 발생하지 않아야하며 최종적으로는 모든 정점들이 이어져야 한다.

 

문제에서 주어진 예제 입력2를 그림을 통해 설명해보겠다.

위 예제에서는 작은 순서 그대로 추가해도 싸이클이 생기는 문제가 없었다.

 

하지만 만약 위 그림에서 3번까지 수행하고, 1번 노드와 2번 노드를 잇는 간선을 추가해야 한다고 가정해보자.

그러면 1 - 2 - 4 간에 싸이클이 발생하기 때문에 해당 간선을 추가해서는 안 된다.

 

그런데 싸이클이 발생한다는 것을 코드로 어떻게 알 수 있을까?

많은 방법이 있겠지만 나는 각 노드마다 최상의 부모 노드를 저장해두는 변수를 사용해 이를 알수 있도록 했다.

 

static int find_parnet(int x){
    if(parent[x]==x) return x;
    else return parent[x] = find_parnet(parent[x]);
}
static void union_parent(int a,int b){
    a=find_parnet(a);
    b=find_parnet(b);
    if(a>b) parent[a]=b;
    else parent[b]=a;
}

위 두 메서드를 사용하여 각 노드의 최상의 부모 노드를 알 수 있도록 구현했다.

 

위 find_parent는 특정 노드가 가지는 최상위 부모 노드를 출력해주는 메서드이고,

아래 union_parnet는 두 노드를 하나의 간선으로 이을 때, 각 노드들의 최상위 부모 노드를 설정해주는 메서드이다.

더 작은 수를 가진 노드를 부모 노드로 가지게 되며, 

이후 특정 노드 간 최상위 부모 노드를 비교했을 때 같다면, 이미 통로가 있는 상태로 간선을 추가하면 싸이클이 발생한다는 것을 알 수 있다.(두 노드 간 최상의 부모 노드가 같다는건 같은 집합에 속하는 것과 같다.)

 

이 방법을 통해 작은 비용부터  '(추가한 간선의 개수)=(노드의 개수) -1' 가 될때까지 차례로 비용 총합을 더하면

우리가 구하는 답이 도출된다.

 

※ 시간 절약 Tip

static int find_parnet1(int x){
    if(parent[x]==x) return x;
    else return find_parnet(parent[x]);
}

static int find_parnet2(int x){
    if(parent[x]==x) return x;
    else return parent[x] = find_parnet(parent[x]);
}

위와 같이 find_parent 메서드가 두 개 있다고 생각해보자.

1~5까지의 노드가 있을 때, 5는 4를, 4는 3을, 3은 2를, 2는 1을, 1은 1을 부모노드로 가진다고 가정해보자.

 

그러면 find_parent1을 썻을 때는 아래 그림에서 위처럼 작동하고,

find_parent2를 썻을 때는 아래 그림에서 아래처럼 작동할 것이다.

따라서 노드의 개수가 많아질 수록 find_parent2 메서드가 효과적임을 알 수 있다.

find_parent1처럼 최상위 부모 노드까지 갈 때가지, 노드를 타고 타고 올라갈 필요없이

 

한 번에 다이렉트로 최상위 부모 노드로 직행할 수 있도록 부모 노드 값을 수정하기 때문이다.

실제로 위 제출은 find_parent2 방식을, 아래 제출은 find_parent1 방식으로 제출한 것으로

2배 이상의 속도 차이가 발생함을 알 수 있다.

 

제출코드

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
    static class Node implements Comparable<Node>{
        int start;
        int end;
        int cost;

        public Node(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            if(this.cost<o.cost) return -1;
            else if(this.cost>o.cost) return 1;
            return 0;
        }
    }
    static PriorityQueue<Node> q = new PriorityQueue<>();
    static int parent[];
    static int find_parnet(int x){
        if(parent[x]==x) return x;
        else return parent[x] = find_parnet(parent[x]);
    }
    static void union_parent(int a,int b){
        a=find_parnet(a);
        b=find_parnet(b);
        if(a>b) parent[a]=b;
        else parent[b]=a;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        parent = new int[T];

        for(int i=0;i<T;++i){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<i+1;++j) st.nextToken();
            for(int j=i+1;j<T;++j){
                int cost = Integer.parseInt(st.nextToken());
                q.offer(new Node(i,j,cost));
            }
            parent[i]=i;
        }

        long resultSum=0;
        int flowCount=0;
        while(!q.isEmpty()){
            Node now = q.poll();

            if(flowCount==T-1) break;

            if(find_parnet(now.start)!=find_parnet(now.end)){
                union_parent(now.start,now.end);
                resultSum+=now.cost;
                ++flowCount;
            }
        }

        bw.write(resultSum+"\n");
        bw.flush();
        bw.close();
    }
}