문제

최소 스패닝 트리

풀이

최소 스패닝 트리를 푸는 알고리즘이 따로 있다고 한다. 크루스칼 알고리즘과 프림 알고리즘 인데 이번에 풀 방법은 크루스칼 알고리즘을 사용할 것이다. 이 알고리즘은 순환이없는 모든 정점을 방문할 수 있는 최소 비용을 계산해야 하는 문제이다.

이 알고리즘은 가장 최소비용의 오름차순으로 정렬하고 순환 루프가 없어야 하기 때문에, 부모가 같은지 를 체크하여 부모가 같지 않으면 연결하는 방식의 알고리즘을 사용한다

1. 부모가 같은지 판정

	private static boolean union(int x, int y) {
        x = findParent(x);
        y = findParent(y);
        if (x == y) {
            return false;
        } else {
            parent[x] = y;
            return true;
        }
    }

    private static int findParent(int x) {
        if (x == parent[x]) {
            return x;
        } else {
            return parent[x] = findParent(parent[x]);
        }
    }

정점을 잇기 전에 부모가 같은지 판정하는 구문이 필요하다. findParent는 x의 부모를 반환하게된다

2. 정점을 연결한다

		for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        for (Point p : arr) {
            if (union(p.current, p.next)) {
                answer += p.cost;
                count++;
                if (count == e - 1) {
                    break;
                }
            }
        }

초기에 parent 배열은 자기자신이 자신을 가리키게 한후에 union에서 정점을 재 설정 해주는 방식으로 진행하게 하면 된다.

전체 코드

전체 코드