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

문제

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

설명

크루스칼 알고리즘 또는 프림 알고리즘 이용하는 문제였는데 나는 크루스칼 알고리즘을 이용하였다.
C언어로 쉽게 풀어쓴 자료구조 책을 참고하면서 union-find 연산을 통해 문제를 해결했다.

1. 간선들을 가중치의 오름차순으로 정렬한 후 가중치가 가장 낮은 간선을 먼저 선택한다.
2. 간선의 시작 노드와 끝 노드의 최상위 노드를 찾는다. (최상위 노드가 없다면 자기 자신이 된다.)
3. 최상위 노드가 다를 경우 union을 통해 두 개의 노드가 속한 집합을 합친 후 가중치를 result에 더해준다.
4. 만약 최상위 노드가 같으면 사이클이 생기는 것이므로 아무것도 하지 않는다.

소스코드

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

class Edge implements Comparable<Edge> {
    int s;
    int e;
    int weight;
	
    public Edge(int s, int e, int weight) {
        this.s = s;
        this.e = e;
        this.weight = weight;
    }
	
    @Override
    public int compareTo(Edge n) { // 가중치를 기준으로 오름차순 정렬
        return this.weight - n.weight;
    }
}

public class Main {
	
    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()); // 간선의 개수

//	ArrayList<Edge> nodeList = new ArrayList<>();
		
        // 우선순위 큐를 사용한다면 Collections.sort를 하지 않아도 가중치를 기준으로 오름차순 정렬이 됨
        PriorityQueue<Edge> pq = new PriorityQueue<>();
		
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
			
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
			
 //         nodeList.add(new Edge(a, b, c));
            pq.add(new Edge(a, b, c));
         }
		
        // 가중치가 작은 순서대로 정렬
//	Collections.sort(nodeList);
		
        parent = new int[V + 1];
		
        // 부모를 자기 자신으로 초기화
        for (int i = 1; i < V + 1; i++) {
            parent[i] = i;
        }

        int result = 0;
        for (int i = 0; i < E; i++) {
//	    Edge edge = nodeList.get(i);
            Edge edge = pq.poll();
			
            // 특정 간선의 시작점과 끝점의 최상위 노드를 찾음
            int rootS = find(edge.s);
            int rootE = find(edge.e);
			
            // 최상위 노드가 같지 않을 경우(간선의 양끝 정점이 같은 집합에 속해있지 않은 경우, 연결되어있지 않은 경우) union
            if (rootS != rootE) {
                union(rootS, rootE);
				
                result += edge.weight; // 가중치를 더함
            }
        }
		
        System.out.println(result);
	
    }

    // 노드 x가 속하는 부모 노드를 찾음
    public static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        else {
            return parent[x] = find(parent[x]);
        }
    }
	
    // 두 개의 노드가 속한 집합을 합침(연결함)
    public static void union(int x, int y) {
        parent[x] = y;

    }
}

GITHUB

https://github.com/MinchaeKwon/BOJ/blob/master/BOJ%231197/src/Main.java