문제

풀이

프림알고리즘을 연습하기 위해 문제를 선택하였다.
저번에는 크루스칼 알고리즘으로 풀었던 문제였는데
프림 알고리즘으로 풀어보았다.

크루스칼 알고리즘은 Edge를 weight(거리) 기준으로 오름차순으로 정렬해서 가능한 Edge들을 그래프에 넣는 것이다.

프림 알고리즘은 PriorityQueue를 이용해 그래프를 확장시켜 나가는 것이다.

코드

프림알고리즘 전체코드

package programmers.high_score_kit.greedy;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class ConnectIslandPrim {
    static ArrayList<Edge>[] graph;

    public int solution(int n, int[][] costs) {
        // 초기화
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        // 초기화 끝

        // 그래프(인접리스트) 만들기
        for (int i = 0; i < costs.length; i++) {
            graph[costs[i][0]].add(new Edge(costs[i][1], costs[i][2]));
            graph[costs[i][1]].add(new Edge(costs[i][0], costs[i][2]));
        }

        return prim(n);
    }

    static class Edge{
        int node;
        int weight;

        public Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    private int prim(int n) {
        int total = 0;
        boolean[] visit = new boolean[n];
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));

        pq.add(new Edge(0, 0));

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

            if(visit[now.node]) continue;
            visit[now.node] = true;
            total += now.weight;

            for (Edge next : graph[now.node]) {
                if(visit[next.node]) continue;
                pq.add(new Edge(next.node, next.weight));
            }
        }

        return total;
    }
}

크루스칼 알고리즘 전체코드

package programmers.high_score_kit.greedy;

import java.util.Arrays;
import java.util.Comparator;

public class ConnectIslandKruskal {
    static int[] parent;

    public int solution(int n, int[][] costs) {
        // edge 들을 정렬
        Arrays.sort(costs, Comparator.comparingInt((int[] c) -> c[2]));
        parent = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        int total = 0;
        for (int[] edge : costs) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];

            // union-find 알고리즘 사용
            int fromParent = findParent(from);
            int toParent = findParent(to);

            // 사이클을 형성하면 pass
            if(fromParent == toParent) continue;
            unionParent(fromParent, toParent);

            total += weight;
            parent[toParent] = fromParent;

        }
        return total;
    }

    private int findParent(int node) {
        if (parent[node] == node) {
            return node;
        }
        parent[node] = findParent(parent[node]);
        return parent[node];
    }

    private void unionParent(int x, int y) {
        int xParent = findParent(x);
        int yParent = findParent(y);

        if(xParent != yParent) parent[y] = xParent;
    }
}

느낀점

프림알고리즘을 구현할 때 pq에 노드를 넣을 때 visit 배열을 true로 바꿔서 자꾸 틀렸다. pq에 노드를 넣으면 그 노드에 대해서 끝내면 안되고 더 weight가 낮은 노드를 발견할 수 있으니 pq에서 꺼냈을 때 visit을 손봐야한다.

이렇게 되었을 때 weight가 작은 것을 뽑아주는 것은 pq가 해주므로 일단 다 pq에 넣는 것이다. 그리고 2번 노드를 뽑았을 때 true로 바꿔주어 2번 노드를 다시 처리하지 않도록 하는 것이다.

---

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%ED%94%84%EB%A6%BCPrim-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98