[Algorithm] 1197 - 최소 스패닝 트리

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

 

 

 

 

 

1. 문제 설명

---

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

 

최소 스패닝 트리의 가중치를 구하는 문제이다. 

최소 스패닝 트리는 그래프의 모든 정점들을 연결해야 하기 때문에 간선의 수는 노드 - 1개를 가진다. 

 

 

예시

 

또한 가중치의 합이 최소로 만들기 위해 사이클을 가지면 안 된다.

1 - 2 / 1 - 3이 연결되어 있을 때 이미 모든 정점을 움직일 수 있기 때문에

2 - 3을 포함하면 가중치에 불필요한 값이 추가되며, 사이클이 발생한다.

 

 

 

2. 접근 방식

---

가중치의 합을 최소로 만들어야 한다 = 가중치가 작은값부터 쏙쏙 골라간다

 

1. 먼저 모든 간선들을 가중치를 기준으로 오름차순 정렬

2. 해당 간선을 포함했을 때 사이클이 안생긴다 → 최소 스패닝 트리에 포함

3. 스패닝 트리의 간선의 개수 = [노드의 개수 - 1]이 되면 멈춤

 

위의 과정의 핵심은 '사이클을 어떻게 검사하는가' 이다.

 

당연히~ bfs를 먼저 떠올렸다. 

 

이 그림을 기준으로 1 - 3 이 사이클이 없는지 검사하기 위해 

• 1부터 bfs 탐색을 시작해서 큐에서 꺼낸 값이 3이면 사이클이 있다.
• 3이 나오지 않으면 사이클이 없다.

간단하게 생각했다.

 

 

 

 

메모리 초과가 떴다. 

문제에서 정점의 개수는 최대 1만개라고 제한해두었기 때문에 bfs로 접근하면

정점 = V (최대 10,000) , 간선 = E (최대 100,000)이므로 최악의 경우 O(1000000000.......

 

안될 수 밖에 없다 ^^..

 

▼ 망한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static List<Integer>[] graph;
    public static int[][] arr;
    public static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray(); // 정점 개수, 간선 개수

        graph = new ArrayList[input[0] + 1];
        for (int i = 0; i < input[0] + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        arr = new int[input[1]][3];
        for (int i = 0; i < input[1]; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

        // 가중치를 기준으로 오름차순 정렬
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a1, int[] a2) {
                return Integer.compare(a1[2], a2[2]);
            }
        });

        int sum = 0;
        int count = 0;

        visited = new boolean[input[0] + 1];
        for (int i = 0; i < arr.length; i++) {
            Arrays.fill(visited, false);

            if (!isCycle(input[0], arr[i][0], arr[i][1])) {
                graph[arr[i][0]].add(arr[i][1]);
                graph[arr[i][1]].add(arr[i][0]);
                sum += arr[i][2];
                count++;
            }

            if (count == input[0] - 1) break;
        }

        System.out.println(sum);
    }

    public static boolean isCycle(int v, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while(!queue.isEmpty()) {
            int n = queue.poll();

            if(n == end) return true;

            for(Integer i : graph[n]) {
                if(!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }

        return false;
    }
}

 

 

사이클을 효과적으로 검사하려면 💡💡💡 Kruskal 알고리즘 (Union find) 💡💡💡를 활용해야한다. 

핵심 알고리즘은 "같은 집합에 속한 노드끼리는 연결하지 않는다" 가 된다.

 

구성요소는 크게 3가지이다. 

① parent 배열 : 각 노드가 속한 집합의 대표(루트)를 저장

int[] parent = new int[n];
for(int i = 0; i < n; i++) parent[i] = i; // 자기자신만 갖도록 초기화

 

 

② find 메소드 : 노드가 속한 집합의 대표를 반환

 public static int find(int x) {
    if(parent[x] == x) return parent[x];
    return parent[x] = find(parent[x]);
}

 

 

③ union 메소드 : 두 집합을 하나로 합침

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

    if(a != b) parent[b] = a; // b를 a에 합치기
}

 

 

 

가중치를 기준으로 오름차순 정렬하면 아래와 같다. 

노드	노드	가중치
1	2	1
1	3	2
2	3	3

 

parent 배열은 초기화를 마치면 자기 자신을 갖는다.

즉, 각 집합의 대표가 자신이 되는 것이다.

1

2

3

 

 

가장 가중치가 작은 [ 노드 1 - 노드 2 ] 가 사이클이 있는지 검사해보자.

노드1 집합 대표와 노드2 집합 대표가 같다면 사이클이 존재한다고 판단한다.

if(find(1) == find(2)) = 사이클 O

 

노드1 집합 대표는 자기 자신인 1

노드2 집합 대표는 자기 자신인 2

 

둘은 서로 다른 값을 가지기 때문에 사이클이 존재하지 않는다.

사이클이 존재하지 않는다면 두 집합을 합친다. 

사이클 X → union(1, 2)

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

    if(a != b) parent[b] = a; // b를 a에 합치기
}

 

노드1과 노드2 집합 대표는 서로 다르기 때문에 parent[2] = 1이 되므로

노드2 집합의 대표는 1이 된다. (노드1, 노드2 집합이 합쳐진 것)

 

이를 코드로 구현하면 아래와 같다. 

 

 

 

3. 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static List<Integer>[] graph;
    public static int[][] arr;
    public static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray(); // 정점 개수, 간선 개수

        graph = new ArrayList[input[0] + 1];
        for (int i = 0; i < input[0] + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        arr = new int[input[1]][3];
        for (int i = 0; i < input[1]; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

        // 가중치를 기준으로 오름차순 정렬
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a1, int[] a2) {
                return Integer.compare(a1[2], a2[2]);
            }
        });

        int sum = 0;
        int count = 0;
        parent = new int[input[0] + 1]; // union find용 배열

        // 초기화
        for(int i = 0; i < input[0] + 1; i++) parent[i] = i;
        for(int i = 0; i < arr.length; i++) {
            // 사이클 검사
            if(find(arr[i][0]) != find(arr[i][1])) {
                union(arr[i][0], arr[i][1]);
                sum += arr[i][2];
                count++;
            }

            if(count == input[0] - 1) break;
        }

        System.out.print(sum);
    }

    // 집합 대표 찾기
    public static int find(int x) {
        if(parent[x] == x) return parent[x];
        return parent[x] = find(parent[x]);
    }

    // 두 집합 합치기
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a != b) parent[b] = a; // b를 a에 합치기
    }
}