[프로그래머스/lv3] 섬 연결하기

문제

n개의 섬이 있고, 각 섬 사이를 잇는 다리 비용이 주어진다. 모든 섬이 서로 연결되도록 다리를 건설할 때, 건설 비용의 합이 최소가 되도록 하는 값을 구하는 것이다. 단, 다리는 양방향으로 이동 가능하며, 직접 연결되지 않아도 다른 섬을 거쳐 연결되면 된다.

프로그래머스 - 섬 연결하기 (Lv.3)

풀이 핵심

모든 노드를 최소 비용으로 연결하는 MST(최소 신장 트리) 문제다.

MST 문제의 경우 두 가지 풀이 방법이 있는데 두 방법 모두 풀어 보겠다.

프림(Prim) 알고리즘 풀이

프림은 Greedy 한 알고리즘으로 n이라는 섬으로 가기 위해 가장 낮은 비용을 지불 할 수 있는 경로를 찾는다.

한번 경로가 확정된 Node는 건드리지 않으며, 확정 Node와 연관된 다른 Node들 중에서 또 다시 가장 낮은 경로와 목적지를 찾아 이 과정을 반복한다.

구현에 있어서 Graph를 표현하기 위해 이중 List 배열인 List<List<int[]» graph를 사용하였다. 섬과의 연결은 양방향이기에 costs 배열에서 추출한 양쪽 값을 세팅해주었다.

		// start node를 기점으로 end에 value만큼 추가  
		graph.get(start).add(new int[] {end, value});  
		graph.get(end).add(new int[]{start, value});  

또한 가장 낮은 섬과 비용을 찾기 위해 PriorityQueue를 사용하여 경로를 관리하였다.

 PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> a[1] - b[1]);  
 
	 pq.offer(new int[] {0, 0});  

	while (!pq.isEmpty()) {  
		int[] node = pq.poll();  
		int dest = node[0];     int cost = node[1];  

		if (visited[dest])  
			continue;  

		visited[dest] = true;  
		ans += cost;  

		for (int[] next : graph.get(dest)) {  
			pq.offer(next);  
		}
	}

Prim 전체 코드

  
import java.util.*;  
  
public class Solution {  
  
    public int solution(int n, int[][] costs) {  
        int ans = 0;  
        List<List<int[]>> graph = new ArrayList<>();  
        PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> a[1] - b[1]);  
        boolean[] visited = new boolean[n];  
  
        // 초기 start 섬 설정  
        for (int i = 0; i < n; i++)  
            graph.add(new ArrayList<int[]>());  
  
        for (int i = 0; i < costs.length; i++) {  
            int start = costs[i][0];  
            int end = costs[i][1];  
            int value = costs[i][2];  
  
            // start node를 기점으로 end에 value만큼 추가  
            graph.get(start).add(new int[] {end, value});  
            graph.get(end).add(new int[]{start, value});  
        }  
  
        pq.offer(new int[] {0, 0});  
  
        while (!pq.isEmpty()) {  
            int[] node = pq.poll();  
            int dest = node[0];     int cost = node[1];  
  
            if (visited[dest])  
                continue;  
  
            visited[dest] = true;  
            ans += cost;  
  
            for (int[] next : graph.get(dest)) {  
                pq.offer(next);  
            }  
        }  
  
        return ans;  
    }  
}

크루스칼 알고리즘(Kruskal Algorithm) 풀이

Graph를 그리는 프림과 달리 크루스칼은 훨씬 간단하게 구현할 수 있는데, 가장 낮은 간선을 선택하고 그 간선을 선택했을 때 Cycle이 형성되는지 확인을 반복하는 방식이다. 가장 낮은 간선의 경우 제공되는 costs 자체를 value 기준으로 정렬하고. 싸이클의 경우 union-find 알고리즘을 사용하여 판별한다.

값 기준 정렬과 싸이클 판별

    // 값 기준 정렬  
    Arrays.sort(costs, (a, b) -> a[2] - b[2]);  
  


public boolean union(int a, int b) {  
    int aRoot = find(a);  
    int bRoot = find(b);  
  
    if (aRoot == bRoot)  
        return true;  
  
    parent[aRoot] = bRoot;  
    return false;  
}  
  
public int find(int n) {  
    if (n == parent[n])  
        return n;  
  
    return find(parent[n]);  
}

Kruskal 전체 코드

public int solution(int n, int[][] costs) {  
    int ans = 0;  
    parent = new int[n];  
  
    for (int i = 0; i < n; i++)  
        parent[i] = i;  
  
    // 값 기준 정렬  
    Arrays.sort(costs, (a, b) -> a[2] - b[2]);  
  
    for (int i = 0; i < costs.length; i++) {  
        int a = costs[i][0];  
        int b = costs[i][1];  
  
        if (union(a, b))  
            continue;  
  
        ans += costs[i][2];  
    }  
  
    return ans;  
}  
  
public boolean union(int a, int b) {  
    int aRoot = find(a);  
    int bRoot = find(b);  
  
    if (aRoot == bRoot)  
        return true;  
  
    parent[aRoot] = bRoot;  
    return false;  
}  
  
public int find(int n) {  
    if (n == parent[n])  
        return n;  
  
    return find(parent[n]);  
}

표로 정리

	프림	크루스칼
핵심	노드 중심, 연결된 곳에서 가장 싼 간선 선택	간선 중심, 전체 간선 중 싼 것부터 선택
자료구조	인접 리스트 + PQ + visited[]	간선 정렬 + Union-Find
복잡도	O(ElogV)	O(ElogE)
추천 상황	간선이 많을 때	간선이 적을 때, 코드 간결함