b1197. 최소 스패닝 트리

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

 

 

 

크루스칼 알고리즘을 활용하여 문제를 풀이하였다.

최근 문제 풀이한 것 중에서 크루스칼이 있었고 간선을 가중치기준으로 정렬하여

풀었던 기억이 있어 그방식대로 풀었다.

 

풀이과정은 비교적 간단하고

이번 문제 풀이에서 기억에 남는것은  union find 를 활용할 때

경로 압축이다.

 

find() 함수에서 if(p[a] == a) 일때 return a를 하는것이아니라
if(p[a]!=a) 일때 p[a] = find(a)를 해주고 return p[a] 를 하게되면 정점의

갯수가 많아지고 간선이 많아지더라도 시간복잡도가 확실히 줄어든 다는점을

알게되었다.

 

예를들어 정점이 6개고 parent 배열이 union(1, 2), union(2, 3) union(3, 4) union(4, 5)

union(5, 6) 과정을 수행했을때 경로 압축을 하지않으면

parent: [0, 1, 1, 2, 3, 4, 5, 6]

가되지만 경로압축을 하게되면

parent: [0, 1, 1, 1, 1, 1, 1]

이리 된다. 이효과는 find 를 호출할 일이 많은 union find 알고리즘에서 

시간복잡도 측면에서 큰 효과가 있다. 

 

이번 문제에서또한 경로압축을 하지 않았을때 시간초과가 났지만

경로압축을 하였더니 통과할 수 있었다.

 

이번 문제는 크루스칼 알고리즘 이외에도 프림알고리즘으로도 문제를 풀이 할 수 있는데

간선의 갯수가 적으면 크루스칼알고리즘이 효율적이나 

간선의 갯수가 많아지면 간선정렬하는데 있어 시간복잡도가 높아지기 때문에

프림알고리즘을 쓰는것이 더 효율적인 문제였다고 볼 수 있다.

 

아래에 프림알고리즘의 코드를 첨부한다.

 

 

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

public class Main {
    private static int[] p;
    private static int  find(int a){
        if(p[a]!=a)
            p[a] = find(p[a]);
        return p[a];
    }
    private static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a!= b)
            p[b] = a;
    }
    static class Road{
        int from;
        int to;
        int degree;
        public Road(int from, int to, int degree){
            this.from = from;
            this.to = to;
            this.degree = degree;
        }
    }
    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();
        int V = input[0];
        int E = input[1];
        Road[] road = new Road[E];
        int answer = 0;
        p = new int[V+1];
        for(int i = 0 ; i < V ; i++)
            p[i] = i;

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

        Arrays.sort(road,(o1, o2) -> o1.degree-o2.degree);

        for(int i = 0 ; i < E ; i++){
            if(find(road[i].from) != find(road[i].to)) {
                union(road[i].from, road[i].to);
                answer += road[i].degree;
            }
        }
        System.out.println(answer);
    }
}

 

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

public class Main {
    static int V,E;
    static List<Edge>[] list;
    static int[] distance;
    static boolean[] check;
    static class Edge implements Comparable<Edge> {
        int e;
        int w;
        public Edge(int e, int w) {
            this.e = e;
            this.w = w;
        }
        @Override
        public int compareTo(Edge edge) {
            return this.w - edge.w;
        }

    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        list = new List[V+1];
        for (int i = 0; i <= V; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list[s].add(new Edge(e,w));
            list[e].add(new Edge(s,w));
        }

        distance = new int[V+1];
        check = new boolean[V+1];

        Arrays.fill(distance,Integer.MAX_VALUE);
        distance[1] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1,0));

        int count = 0;
        int result = 0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if(check[cur.e]) continue;
            check[cur.e] = true;
            count++;
            result += cur.w;
            if(count == V) {
                break;
            }

            for (int i = 0; i < list[cur.e].size(); i++) {
                Edge next = list[cur.e].get(i);
                if(check[next.e]) continue;
                pq.offer(next);
            }

        }
        System.out.println(result);


    }
}