99클럽 코테 스터디 20일차 TIL [크루스칼, 프림]

- 오늘의 학습 키워드 : 크루스칼, 프림

[문제 이름 :   섬 연결하기 (프로그래머스 Greedy, Lv 3) ]

문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/42861

 

내가 작성한 코드는 아래와 같다.

import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        ArrayList<Pair>[] graph = new ArrayList[n];
        
        for(int i=0; i<n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 인접 그래프 정보 저장
        for(int[] cost : costs) {
            graph[cost[0]].add(new Pair(cost[1], cost[2]));
            graph[cost[1]].add(new Pair(cost[0], cost[2]));
        }
        
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        
        visited[0] = true;
        for(Pair p : graph[0]) {
            pq.offer(new Pair(p.endNode, p.cost));
        }

        while(!pq.isEmpty()) {
            Pair cur = pq.poll();
            int endNode = cur.endNode;
            int cost = cur.cost;
            
            if(visited[endNode]) continue;
            
            visited[endNode] = true;
            answer += cost;
            
            for(Pair pa : graph[endNode]) {
                if(!visited[pa.endNode]) {
                    pq.offer(new Pair(pa.endNode, pa.cost));
                }
            }
        }
        
        return answer;
    }
    
    static class Pair implements Comparable<Pair>{
        int endNode;
        int cost;
        
        Pair(int endNode, int cost) {
            this.endNode = endNode;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Pair o) {
            return this.cost - o.cost;
        }
    }
}

[풀이 과정]

1. 인접리스트로 그래프 정보를 저장한다.

2. 최소 비용을 구해야 하기 때문에, 비용을 오름차순으로 가지도록 정렬한다. (Pair라는 클래스와 PriorityQueue 사용)

3. 방문 여부를 따지며, 최소 비용을 더해준다.

 

풀이 시간 : 30분

 

정통 방식은 유니온-파인드를 이용한 크루스칼 알고리즘으로 풀어보는 것 같다.

유니온-파인드를 사용하게 되면, 사이클이 형성되는 것을 방지할 수 있다.

실제 계산을 해보면, 1 + 1 + 2 가 되어 answer=4가 되고, parent배열의 값은 모두 0으로 저장되어, 그래프가 최소로 연결되는 것을 확인할 수 있다.

import java.util.*;
class Solution {
    static int[] parent;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        for(int i=0; i<n; i++) {
            parent[i] = i;
        }
        
        Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);
        // 크루스칼 알고리즘
        for(int i=0; i<costs.length; i++) {
            int a = find(costs[i][0]);
            int b = find(costs[i][1]);
            if(a != b) {
                union(a,b);
                answer += costs[i][2];
            }
        }
        return answer;
    }
    
    static int find(int a) {
        if(parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }
    
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }
}

 

내일은 dfs, 백트래킹 관련 문제를 풀어보고자 한다.