코딩 테스트 [그래프] - 최소 신장 트리 구하기

최소 신장 트리(최소 스패닝 트리)는 주어진 그래프의 모든 노드들을 연결하는 부분 그래프 중 그 가중치의 합이 최소인 트리를 말한다. 그래프가 주어졌을 때 그 그래프의 최소 신장 트리를 구하는 프로그램을 작성하시오.

(시간 제한 2초)

---

입력

1번째 줄에 노드의 개수 V(1 ≤ V ≤ 10,000)와 에지의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 에지와 관련된 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 노드와 B번 노드가 가중치 C인 에지로 연결돼 있다는 의미다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 노드는 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 노드 사이에 경로가 있다. 최소 신장 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

1번째 줄에 최소 신장 트리의 가중치를 출력한다.

예제 입력
3 3	// 노드 개수, 에지 개수
1 2 1
2 3 2
1 3 3

예제 출력
3

---

1단계 - 문제 분석하기

최소 신장 트리를 구하는 기본적인 문제이다.

2단계 - 손으로 풀어 보기

1 에지 리스트에 에지 정보를 저장한 후 부모 노드 데이터를 초기화한다. 최소 신장 트리는 에지 중심의 알고리즘이므로 데이터를 에지 리스트를 활용해 저장해야 한다. 사이클 생성 유무를 판단하기 위한 유니온 파인드용 부모 노드도 초기화한다.

2 현재 미사용 에지 중 가중치가 가장 작은 에지를 선택하고, 이 에지를 연결했을 때 사이클의 발생 유무를 판단한다. 사이클이 발생하면 생략하고, 발생하지 않으면 에지값을 더한다.

3 과정 2에서 에지를 더한 횟수가 'V(노드 개수) - 1'이 될 때까지 반복하고, 반복이 끝나면 에지의 가중치를 모두 더한 값을 출력한다.

3단계 - sudo코드 작성하기

N(노드 수), M(에지 수)
parent(대표 노드 저장 배열)
queue(에지 정보를 저장할 우선순위 큐)

for(M만큼 반복)
{
	queue에 에지 정보 저장
}

while(사용한 에지 수가 N-1이 될 때까지)
{
	큐에서 에지 정보 가져오기
    find로 에지 시작점과 끝점의 부모 노드가 다르면 union연산 수행
    에지의 가중치를 정답 변수에 더하기
}

정답 변수 출력하기

union(a, b)
{
	find로 a와 b의 대표 노드 찾기
    두 원소의 대표 노드끼리 연결하기
}

find(a)
{
	a가 대표 노드면 리턴하기
    아니면 a의 대표 노드값을 find(parent[a])값으로 저장
}

4단계 - 코드 구현하기

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

public class Q64 {
    public static int[] parents;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        parents = new int[N+1];
        PriorityQueue<Edge64> queue = new PriorityQueue<>();

        for(int i = 1; i < N+1; i++){
            parents[i] = i;
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            queue.add(new Edge64(s, e, v));
        }

        int result = 0;
        int countNode = 0;
        while(countNode != N-1){
            Edge64 now = queue.poll();
            if(find(now.s) != find(now.e)){
                union(now.s, now.e);
                result += now.v;
                countNode++;
            }
        }

        System.out.println(result);
    }

    public static void union(int a, int b){
        a = find(a);
        b = find(b);

        if(a != b)
            parents[b] = a;
    }

    public static int find(int a){
        if(a == parents[a])
            return a;
        else
            return parents[a] = find(parents[a]);
    }
}
class Edge64 implements Comparable<Edge64>{
    int s;
    int e;
    int v;
    Edge64(int s, int e, int v){
        this.s = s;
        this.e = e;
        this.v = v;
    }

    @Override
    public int compareTo(Edge64 o) {
        return this.v - o.v;
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편