그리디. 섬연결하기

Jung In Lee·2023년 2월 14일
0

문제

0부터 n - 1까지 섬들을 모두 연결하는 최소 비용을 찾는 문제.

해결방향성

처음에 다익스트라로 풀이를 시도했다. 아무래도 가중치 문제다 보니, 최단거리를 접근하는 방식으로 시도했는데, 다익스트라는 한 점에서 한 점까지 최단경로를 찾는데 집중한다. 또한, 여러군데 다익스트라로 푸는 방법을 찾아보았지만, 한 점 한 점 이동할때마다 최소 간선을 선택하는 방식으로 선택하고, 모든 정점에서 시도하는 방식으로 해보았다. 하지만 그래도 안찾아지는 경우가 생겨서, 최소 간선을 찾는것에 집중하고, 가중치 순환을 방지하는 유니온 파인드를 사용하였다.
추가. 프림 알고리즘을 사용할수도있다. 프림알고리즘은 유니온 파인드는 사용하지않는다.

코드

  • 이전코드 : 다익스트라 실패
import java.util.*;


class Solution {
     static class Vertex implements Comparable<Vertex>{
        int num;
        int weight;

        public Vertex(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }

        @Override
        public int compareTo(Vertex v) {
            return this.weight - v.weight;
        }
    }
    private static ArrayList<ArrayList<Vertex>> graph;
    private static int min;
    private static boolean[] visited;
    public int solution(int n, int[][] costs) {
        min = Integer.MAX_VALUE;
        // costs[N][0] : 시작점
        // costs[N][1] : 끝점
        // costs[N][2] : 가중치

        // 그래프 연결
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) { // n : 간선의 개수
            int start = costs[i][0];
            int end = costs[i][1];
            int weight = costs[i][2];

            graph.get(start).add(new Vertex(end, weight));
            graph.get(end).add(new Vertex(start, weight));
        }


        for (int i = 0; i < n; i++) {
            visited = new boolean[n];

            dijkstra(n, i);

            int sum = 0;
            for (int j = 0; j < n; j++) {
                if (visited[j]) {
                    sum += minWeight[j];
                }
            }
            min = Math.min(min, sum);
        }

        return min;
    }

    private static int[] minWeight;
    private void dijkstra(int n, int start) {
        PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
        minWeight = new int[n];
        Arrays.fill(minWeight, Integer.MAX_VALUE);
        priorityQueue.add(new Vertex(start, 0));
        minWeight[start] = 0;


        while (!priorityQueue.isEmpty()) {
            Vertex poll = priorityQueue.poll();
            int pollNum = poll.num;
            //int pollWeight = poll.weight;


            //if (visited[pollNum]) continue;
            visited[pollNum] = true;

            for (Vertex endVertex: graph.get(pollNum)) {
                // 끝점 정보들
                int endNum = endVertex.num;
                int endWeight = endVertex.weight;

                // 끝점 최단거리가 endWeight 보다 크면
                if (minWeight[endNum] > endWeight && !visited[endNum]) {
                    minWeight[endNum] = endWeight;
                    priorityQueue.add(new Vertex(endNum, endWeight));
                }
            }
        }

    }
}
  • 수정코드 : 크루스칼, 유니온 파인드
import java.util.*;
public class Solution {
    static int[] parent; // 유니온 파인드 부모 배열
    public int solution(int n, int[][] costs) {
        // 크루스칼 알고리즘 : 간선 중심, 가중치 오름차순 정렬
        // costs : 시작, 도착, 가중치
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[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 cost = edge[2];

            int fromParent = findParent(from);
            int toParent = findParent(to);

            // 부모노드가 같으면(같은 그래프에 속하면)
            // 간선을 선택하지않는다.
            if (fromParent == toParent) continue;

            total += cost;
            // 간선을 연결해 두 노드가 같은 그래프에 속하게됨.
            // -> 부모노드 갱신 (같은 부모노드로)
            parent[toParent] = fromParent;  
        }
        return total;
    }

    // 부모노드가 자기자신과 같은 노드를 찾을때까지 재귀호출
    private int findParent(int node) {
        if (parent[node] == node) return node;
        return parent[node] = findParent(parent[node]);
    }


    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] costs = {{0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8}};
        int n = 4;
        System.out.println(s.solution(n,costs));

    }
}
  • 프림 알고리즘
import java.util.*;


class Solution {
    static int total;
    static ArrayList<ArrayList<Vertex>> graph;
    
    static class Vertex implements Comparable<Vertex>{
        int num;
        int weight;

        public Vertex(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }

        @Override
        public int compareTo(Vertex o) {
            return this.weight - o.weight;
        }
    }
   
    public int solution(int n, int[][] costs) {
          graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

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

            graph.get(from).add(new Vertex(to, cost));
            graph.get(to).add(new Vertex(from, cost));
        }

        prim(0, n);
        return total;
    }
    private void prim(int start, int n) {
        boolean[] visited = new boolean[n];

		// 우선순위 큐를 사용한다는 점에서 다익스트라와 비슷하게 느껴지기도한다.
        // 하지만, 다익스트라는 정점간의 최단거리를 구하는것이고, 프림알고리즘은 각 점을 모두
        // 연결할수있는 그리디 방식이다.
        PriorityQueue<Vertex> pq = new PriorityQueue<>();
        // 시작점 대입.
        pq.add(new Vertex(start, 0));

		// pq가 빌때까지 반복
        while (!pq.isEmpty()) {
            Vertex poll = pq.poll();
            int pollNum = poll.num;
            int pollWeight = poll.weight;

            if (visited[pollNum]) continue;
            // visit 하고 
            visited[pollNum] = true;
            // 최소 가중치 더함.
            total += pollWeight;
            // 끝점 방문하지않았으면 방문하고 pq에 넣음.
            // pq가 자동으로 정렬해줌.
            for (Vertex endVertex : graph.get(pollNum)) {
                if (visited[endVertex.num]) continue;
                pq.add(endVertex);
            }
        }
    }
    
}

결론

최소 가중치의 합을 구하는 최소 스패닝 트리중 크루스칼 알고리즘을 배울수있어서 좋았고, 유니온 파인드 문제를 접할수있어서 좋았다.
참고 블로그:
https://maetdori.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0
블로그2: 크루스칼과 프림
https://ongveloper.tistory.com/376

profile
Spring Backend Developer

0개의 댓글