(알고리즘 스터디) (Programmers) 섬 연결하기 🏝️

🌟 프로그래머스 /  Level3 / 섬 연결하기

📃 문제

프로그래머스

🚫 제한 사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

👀 입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

🤔 풀이 방법

1️⃣ 다익스트라 (실패 🙅‍♀️)

➡️ 다익스트라를 통해 특정 아무 섬에서 출발하여 최소 비용의 합을 출력하면 될 것 이라고 생각했고, 아래와 같은 코드를 작성하였다.

import java.util.Queue;
import java.util.PriorityQueue;
import java.util.ArrayList;

// Node 클래스 정의
class Node implements Comparable<Node> {
    int index;
    int cost;
    
    public Node (int index, int cost) {
        this.index = index;
        this.cost = cost;
    }
    
    @Override
    public int compareTo (Node o) {
        return Integer.compare(this.cost, o.cost);
    }
}

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        // 최소거리를 담을 배열
        int[] minDist = new int[n];
        // 최소비용을 담을 배열
        int[] minCost = new int[n];
        
        // 배열 초기화
        int max = Integer.MAX_VALUE;
        
        for (int i=0; i<n; i++) {
            minDist[i] = max;
        }
        
        // 입력값 처리        
        ArrayList<Node>[] graph = new ArrayList[n];
        for (int i=0; i<n; i++) graph[i] = new ArrayList<>(); // 초기화
        
        for(int[] c : costs) {
            graph[c[0]].add(new Node(c[1], c[2]));
            graph[c[1]].add(new Node(c[0], c[2]));
        }
        
        // 시작점 설정
        Queue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[n];
        
        minDist[0] = 0;
        pq.add(new Node(0, 0));
        
        // 탐색 시작
        while(!pq.isEmpty()) {
            int nowVertex = pq.poll().index;
            
            if (visited[nowVertex]) continue;
            visited[nowVertex] = true;
            
            for (Node next : graph[nowVertex]) {
                if (minDist[next.index] > minDist[nowVertex] + next.cost) {
                    // 최단 거리 값 갱신
                    minDist[next.index] = minDist[nowVertex] + next.cost;
                    // 최소 비용 값 갱신
                    minCost[next.index] = next.cost;
                    // Queue 삽입
                    pq.offer(new Node(next.index, minDist[next.index]));
                }
            }
        }
        
        // 값 계산
        for (int i=1; i<n; i++) {
            answer += minCost[i];
            // System.out.printf("%d번째 : %d\n", i, minCost[i]);
        }
        
        return answer;
    }
}

➡️ 이렇게 될 경우 출발 지점마다 최소 비용이 다르기 때문에 반례가 생겨 실패한다.

2️⃣ 다익스트라를 모든 출발 점에서 진행 ➡️ 플로이드 워셜 (실패 🙅‍♀️)

➡️ 1️⃣ 풀이에서 한 시작점만 정해서 문제가 생긴 것 이므로 다익스트라를 모든 섬에서 실행시켜 플로이드 워셜의 형태로 구현하였다.

import java.util.Queue;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Collections;

// Node 클래스 정의
class Node implements Comparable<Node> {
    // (클래스 정의 코드 생략)
}

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        // 최소거리를 담을 배열
        int[][] minDist = new int[n][n];
        // 최소비용을 담을 배열
        int[][] minCost = new int[n][n];
        // 정답값들을 담을 배열
        ArrayList<Integer> answers = new ArrayList<>();
        
        // 배열 초기화
        int max = Integer.MAX_VALUE;
        
       for (int[] dist : minDist) {
           for (int i=0; i<n; i++) {
               dist[i] = max;
           }
       }
        
        // 입력값 처리        
        ArrayList<Node>[] graph = new ArrayList[n];
        for (int i=0; i<n; i++) graph[i] = new ArrayList<>(); // 초기화
        
        for(int[] c : costs) {
            graph[c[0]].add(new Node(c[1], c[2]));
            graph[c[1]].add(new Node(c[0], c[2]));
        }
        
        // 시작점 설정
        Queue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[n];
        
        for (int start=0; start<n; start++) {
            minDist [start][start] = 0;
            pq.add(new Node(start, 0));
            
            // 탐색 시작
            while(!pq.isEmpty()) {
                int nowVertex = pq.poll().index;

                if (visited[nowVertex]) continue;
                visited[nowVertex] = true;

                for (Node next : graph[nowVertex]) {
                    if (minDist[start][next.index] > minDist[start][nowVertex] + next.cost) {
                        // 최단 거리 값 갱신
                        minDist[start][next.index] = minDist[start][nowVertex] + next.cost;
                        // 최소 비용 값 갱신
                        minCost[start][next.index] = next.cost;
                        // Queue 삽입
                        pq.offer(new Node(next.index, minDist[start][next.index]));
                    }
                }
            }
            
            // 값 계산
            int sum = 0;
            for (int i=0; i<n; i++) {
                sum += minCost[start][i];
            }
            answers.add(sum);
            
            visited = new boolean[n];
        }

        return Collections.min(answers);
 }
}

➡️ 이렇게 코드를 작성해도 통과하지 못하는 테스트 케이스들이 있었다. 애초에 접근 자체가 잘못되었던 것이다.

3️⃣ 탐욕법 (성공 🙆‍♀️)

➡️ 생각을 바꿔서 다음과 같이 정의하였다.

① : 모든 섬 연결 정보를 저장한다.
② : 가장 비용이 많이 드는 연결을 끊어낸다. (Greedy 개념)
③ : 연결을 끊어내도 섬이 모두 연결되는지 확인한다. (DFS)
④-1 : 연결되면 해당 비용은 절감이 가능하므로 연결을 끊고, 계산에서 제외시킨다. 
④-2 : 연결되지 않으면 해당 연결을 원상복구하고, 비용에 포함시킨다.

➡️ ② 를 코드로 구현하기 위해 우선순위 큐를 사용하였다. costs 입력값들을 우선순위 큐에 담으며 내림차순 정렬이 되도록 하였는데, 이를 위해 Node 클래스 선언에서 Comparable 인터페이스를 구현하여 내림차순으로 기준을 정립해주었다.

class Node implements Comparable<Node> { // Comparable 인터페이스 도입
    public int start;
    public int end;
    public int cost;
    
    public Node (int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node o) {
        return Integer.compare(o.cost, this.cost); // 내림차순
    }
}

Queue<Node> pq = new PriorityQueue<>();

for (int[] cost : costs) {
    // 우선순위 큐에 Node 담기
    pq.offer(new Node(cost[0], cost[1], cost[2]));
}

➡️ 불규칙했던 입력값들이 내림차순으로 정리된 것을 볼 수 있다.

➡️ 위와 같은 과정을 통해서 비용이 큰 값부터 연결을 확인하며 최대한 연결을 끊어내었고, 테스트 케이스 모두 통과 하였다.

실행 결과

💻 풀이 코드

import java.util.Queue;
import java.util.PriorityQueue;
import java.util.ArrayList;

class Node implements Comparable<Node> {
    public int start;
    public int end;
    public int cost;
    
    public Node (int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node o) {
        return Integer.compare(o.cost, this.cost); // 내림차순
    }
}
class Solution {
    public static boolean[][] graph;
    public static boolean[] visited;
    public static int cnt = 1;
    public static boolean done = false;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        visited = new boolean[n];
        
        // (1) 입력값 담기
        Queue<Node> pq = new PriorityQueue<>();
        
        graph = new boolean[n][n];

        for (int[] cost : costs) {
            // 우선순위 큐에 Node 담기
            pq.offer(new Node(cost[0], cost[1], cost[2]));
            // 인접 행렬에 연결 반영
            graph[cost[0]][cost[1]] = true;
            graph[cost[1]][cost[0]] = true;
        }
        
        // 우선순위 큐 입력확인 : 내림차순 형태
        System.out.printf("우선 순위 큐 확인 : ");
        for (Node node : pq) {
            System.out.printf("%d " , node.cost);
        }
        System.out.println();
            
        // (2) Greedy 적용하면서 전체 탐색
        while (!pq.isEmpty()) {
            Node node = pq.poll(); // 가장 비용이 큰 노드 [2,3,8]
            
            // 연결 끊기
            graph[node.start][node.end] = false;
            graph[node.end][node.start] = false;
            
            // 연결 가능 탐색
            visited[0] = true;
            
            System.out.printf("%d 빼고 연결 가능 여부 : ", node.cost);
            
            if (isLinked(0, n)) { // 경우 1 : 연결 가능하면 없어도 가능하므로 answer 에 값 추가 안함
                reset(n);
                System.out.println("가능");
                continue;
            }
            
            // 경우2 : 연결 불가능하면 필요한 값이므로 answer 에 값 추가
            reset(n);
            System.out.println("불가능");
            
            // 연결 원상복구
            graph[node.start][node.end] = true;
            graph[node.end][node.start] = true;

            answer += node.cost;
        }
        
        return answer;
    }
    
    // 연결 탐색 : DFS
    public static boolean isLinked(int start, int n) {
        if (done) return true;
        
        for (int i=0; i<n; i++) {
            if (start == i || visited[i]) continue;
            
            if (graph[start][i]) {
                visited[i] = true;
                if (++cnt == n) done = true;
                isLinked(i, n);
            }
        }
        
        if (done) return true;
        
        return false;
    }
    
    // 연결 탐색 후 초기화
    public static void reset(int n) {
        cnt = 1;
        done = false;
        visited = new boolean[n];
    }
}

🧐 추가 공부

1️⃣  크루스칼 알고리즘 (Kruscal)

➡️ 마지막 풀이 방식이 매번 DFS 를 통해 전체 연결여부를 확인해야한다는 점에서 노드의 개수가 많아질 수록 부담 기하급수적으로 늘어날 것이라고 생각했고, 추가적으로 알고리즘을 공부하던 중 최소 신장 트리 개념이 적용된 크루스칼 알고리즘에 대해 알게 되었다. 먼저 신장 트리 (Spanning Tree) 의 조건은 크게 두가지이다.

출처 : https://www.youtube.com/watch?v=Gj7s-Nrt1xE

① 사이클이 존재하지 않는다.
② 모든 정점들이 연결되어있다.

➡️ 위 두가지 조건을 만족하면서 트리를 생성하게 되면 총 간선의 개수가 (n-1) 개가 되고, 이 기본 조건에서 최소 가중치로 간선들을 구성하면 그것을 최소 신장 트리 (MST = Minimum Spanning Tree) 라고 한다.

➡️ 크루스칼 알고리즘의 경우 탐욕법 (Greedy) 를 기본 개념으로 한다. 주어진 간선들에서 최소 비용을 가진 간선부터 확인하며 트리를 구성해간다. 이 때 사용되는 자료구조는 루트 노드를 기록하기 위한 parent 배열이고, 함수는 특정 노드의 루트 노드를 확인하는 findParent() 와 루트 노드가 다른 두 집합을 하나로 묶는 unionParent() 를 정의하여 사용한다. 작동 원리는 아래와 같다.

① : 주어진 간선들을 비용을 기준으로 오름차순 정렬한다.
② : 간선의 두 노드들의 루트 노드를 확인한다.
③-1 : 같으면 연결할 경우 사이클이 발생하므로 넘어간다.
③-2 : 다르면 신장 트리의 조건을 만족하므로 두 집합을 합치고, 비용에 반영한다.
④ : 모든 간선에 대해서 ②,③ 의 과정을 반복한다.

➡️ 적용된 코드는 아래와 같다.

import java.util.ArrayList;
import java.util.Collections;

class Node implements Comparable<Node> { // 노드 클래스 선언
    int indexA, indexB, cost;
    
    public Node (int indexA, int indexB, int cost) {
        this.indexA = indexA;
        this.indexB = indexB;
        this.cost = cost;
    }
    
    @Override
    public int compareTo (Node other) {
        if (this.cost < other.cost) return -1;
        return 1;
    }
}

class Solution {
    // root 노드 값을 담는 배열
    public static int[] parent;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        // parent 배열 초기화
        parent = new int[n];
        for (int i=0; i<n; i++) {
            parent[i] = i;
        }
        
        // 입력값 처리
        ArrayList<Node> vertexList = new ArrayList<>();
        for (int[] cost : costs) {
            vertexList.add(new Node(cost[0], cost[1], cost[2]));
        }
        // 정렬
        Collections.sort(vertexList);
        
        for (int i=0; i<vertexList.size(); i++) {
            int from = vertexList.get(i).indexA;
            int to = vertexList.get(i).indexB;
            int cost = vertexList.get(i).cost;
            // 루트 원소가 같지 않다면 사이클이 발생하지 않는 것이므로 묶음처리
            if (findParent(from) != findParent(to)) {
                union(from, to);
                answer += cost;
            }
        }
        
        return answer;
    }
    
    public static int findParent(int x) {
        if (parent[x] == x) return x;
        return parent[x] = findParent(parent[x]);
    }
    
    public static void union(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }
}

크루스칼 알고리즘 실행 결과