본문 바로가기
알고리즘/백준

1197번 - 최소 스패닝 트리(Prim 알고리즘)

by HWK 2024. 7. 8.

1197번: 최소 스패닝 트리 (acmicpc.net)

 

문제

 

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

 

예제입력

3 3
1 2 1
2 3 2
1 3 3

 

처음에는 트리라는 것을 생각하지 않고, 하나의 경로라는 생각을 했다.

시작점이 다를때 다른 결과가 나올거라는 잘못된 생각을 하게되어 아래처럼 시간복잡도가 큰 코드가 짜여지게 되었다.

더보기
import java.util.*;

class PrimCount implements Comparable<PrimCount> {
    int end;
    int len;
    int count;

    public PrimCount(int end, int len, int count) {
        this.end = end;
        this.len = len;
        this.count = count;
    }

    public void addPrime (PrimCount other) {
        other.count += 1;
    }

    @Override
    public int compareTo(PrimCount other) {
        return Integer.compare(this.len, other.len);
    }
}


public class 최소스패닝트리_1197번_메모리초과 {
    static int V, E;
    static List<PriorityQueue<PrimCount>> routes;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();

        routes = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            routes.add(new PriorityQueue<>());
        }

        for (int i = 0; i < E; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            int C = sc.nextInt();
            routes.get(A).add(new PrimCount(B, C, 0));
        }

        minimumSpanningTree();

        System.out.println(min);

    }

    static void minimumSpanningTree() {
        for (int i = 1; i <= V; i++) {
            boolean[] visited = new boolean[V+1];
            PriorityQueue<PrimCount> pq = new PriorityQueue<>();
            pq.add(new PrimCount(i, 0, 0));
            while (!pq.isEmpty()) {
                PrimCount now = pq.poll();
                if (now.count == V-1) {
                    min = Math.min(min, now.len);
                    break;
                }
                visited[now.end] = true;
                for (PrimCount next : routes.get(now.end)) {
                    if (!visited[next.end]) {
                        pq.add(new PrimCount(next.end, now.len + next.len, now.count+1));
                    }
                }
            }
        }
    }
}

 

잘못 생각한 것도 있지만 Spanning Tree에 대한 개념을 잊은 것 같았다.

아래 블로그들을 참고했고, 서로 연관된 블로그들이다.

 

Spanning Tree

 

Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리이며, n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개다.
하나의 그래프에는 많은 신장 트리가 존재할 수 있다.

모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.

MST

 

Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다.
간선의 가중치의 합이 최소여야 한다.
n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
사이클이 포함되어서는 안된다.

MST 구현 방법에는 Kruskal 알고리즘과 Prim 알고리즘을 사용할 수 있다.

Kruskal 알고리즘의 시간 복잡도 O(elog₂e), Prim 알고리즘의 시간복잡도는 O(n^2)  이다.

고로 적은 숫자의 간선을 가지는 그래프의 경우 Kruscal을, 그래프에 간선이 많이 존재하는 경우엔 Prim을 사용하면 된다.

간선의 개수가 십만개를 넘어가므로 Prim 알고리즘을 사용하기로 했다.

 

Prim 알고리즘은 시작 정점에서부터 출발해 신장트리 집합을 단계적으로 확장하는 방법이다.

과정은 다음과 같다.

위 그림을 보면 센스 있는 사람들은 바로 풀 수 있을 것이다.

난 아직 없는것같다,, 다음은 정답 코드이다.

class Prim implements Comparable<Prim> {
    int end;
    int len;

    public Prim(int end, int len) {
        this.end = end;
        this.len = len;
    }

    @Override
    public int compareTo(Prim other) {
        return Integer.compare(this.len, other.len);
    }
}


public class 최소스패닝트리_1197번 {
    static int V, E;
    static List<PriorityQueue<Prim>> routes;
    static boolean[] visited;
    static int totalCost = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();

        routes = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            routes.add(new PriorityQueue<>());
        }

        for (int i = 0; i < E; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            int C = sc.nextInt();
            routes.get(A).add(new Prim(B, C));
            routes.get(B).add(new Prim(A, C));
        }

        visited = new boolean[V + 1];
        minimumSpanningTree(1);

        System.out.println(totalCost);

    }

    static void minimumSpanningTree(int start) {
        PriorityQueue<Prim> pq = new PriorityQueue<>();
        pq.add(new Prim(start, 0));

        while (!pq.isEmpty()) {
            Prim now = pq.poll();

            if (visited[now.end]) continue;
            visited[now.end] = true;
            totalCost += now.len;

            for (Prim next : routes.get(now.end)) {
                if (!visited[next.end]) {
                    pq.add(next);
                }
            }
        }
    }
}

입력

1. 정점은 양방향 관계이므로, List<PriorityQueue> 형태에 두번( A -> B, B -> A ) 저장해준다.

prim 알고리즘 실행 함수

2. 우선순위 큐를 하나 만들어주고, 시작 정점을 포함시켜준다.

3. 우선순위 큐에 이미 비교되어 저장된 숫자 중 하나를 poll() 해보면,
    지금 정점들과 연결된 간선들 중 가장 작은 간선과 연결된 정점이 나오게 된다.

4. 해당 정점이 이미 그래프에 연결된 상태라면 무시한다. 고리 형태가 나오기 때문이다.

5. 그렇지 않다면, 지금 간선의 길이를 총 합에 더해주며,
    다음 정점과 연결된 정점들(이미 그래프에 연결되지 않아야함)를 우선순위 큐에 포함시켜준다.

6. 3~ 5번 과정을 반복하며, 우선순위 큐가 비게되면, 반목문이 끝나고, 그래프가 완성된다. 최소 가중치도 구해져있다.

 

다음에는 Kruscal 알고리즘을 구현 해보도록 하자