Programmers Lv3, 섬 연결하기[Java, C++]

junto·2024년 7월 8일

Algorithms Graph programmers

programmers

목록 보기

44/66

문제

Programmers Lv3, 섬 연결하기

핵심

그래프 문제로 정점이 최대 100개, 간선이 대략 5000개가 있다. 대략 $O(N^2)$ 이하 알고리즘을 사용한다.
n개의 섬 사이에 다리를 건설하는 비용을 줬을 때 모든 섬을 연결하는 최소 다리 건설비용을 구해야 한다. 즉, 최소 신장 트리를 구하는 문제라고 볼 수 있다. 최소 신장 트리란 모든 정점을 포함하는 부분 그래프 중 간선의 합이 최소인 트리이다. 이는 사이클이 없는 연결그래프로 V-1개 간선을 가진다.
최소 신장 트리를 효율적으로 구하는 크루스칼 알고리즘과 크림 알고리즘을 이용해서 구현해 보도록 한다.

크루스칼 알고리즘

크루스칼 알고리즘은 union-find 알고리즘을 사용하여 사이클을 형성하지 않으면서 최소비용으로 두 정점을 연결하는 그리디 알고리즘의 일종이다.
적용
- 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다.
- 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무것도 하지 않고 넘어간다. u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다.
- 최소 신장 트리에 V-1개의 간선을 추가시켰다면 종료, 그렇지 않다면 그다음으로 비용이 작은 간선을 선택한 후 2번 과정을 반복한다.
시간복잡도
- $O(ElogE)$
같은 그룹인지 아닌지 판단할 때 Union-Find 알고리즘을 이용하면 효율적으로 구할 수 있다.

1. Java

import java.util.*;

class Solution {
    int[] p;
    
    public int find(int x) {
        if (p[x] < 0) return x;
        return p[x] = find(p[x]);
    }

    public boolean isUnioned(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (p[x] == p[y]) p[x]--;
        if (p[x] < p[y]) p[y] = x;
        else p[x] = y;
        return true;
    }
    
    public int solution(int n, int[][] costs) {
        p = new int[104];
        Arrays.fill(p, -1);
        Arrays.sort(costs, (a, b) -> Integer.compare(a[2], b[2]));
        int ans = 0;
        int cnt = 0;
        for (var c : costs) { // a, b, cost
            if (!isUnioned(c[0], c[1]))
                continue;
            ans += c[2];
            ++cnt;
            if (cnt == n - 1) break;
        }
        return ans;
    }
}

2. C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> p(104, -1); 

int find(int x) {
    if (p[x] < 0) 
        return x;
    else
        return p[x] = find(p[x]); 
}

bool is_unioned(int x, int y) {
    x = find(x); 
    y = find(y);
    if (x == y) return false; 
    if (p[x] == p[y])
        --p[x];
    if (p[x] < p[y])
        p[y] = x;
    else
        p[x] = y;
    return true;
}

int solution(int n, vector<vector<int>> costs) {
    
    sort(costs.begin(), costs.end(), [](auto& a, auto& b) {
        return a[2] < b[2];
    });
    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < costs.size(); ++i) {
        auto [a, b, cost] = tie(costs[i][0], costs[i][1], costs[i][2]);
        if (!is_unioned(a, b))
            continue;
        ans += cost;
        ++cnt;
        if (cnt == n - 1) break;
    }
    return ans;
}

프림 알고리즘

프림 알고리즘은 우선순위 큐를 이용하여 이미 최소 신장 트리에 포함된 정점을 기준으로 포함되지 않은 정점 중 가장 비용이 적은 간선을 선택하여 정점을 연결하는 그리디 알고리즘의 일종이다. 최소 신장 트리를 확장해 나가는 방식으로 진행되기에 사이클이 형성되지 않는다.
적용
- 임의의 정점을 선택해 최소 신장 트리에 추가, 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가한다.
- 우선순위 큐에서 비용이 가장 작은 간선을 선택한다.
- 해당 간선이 최소 신장 트리에 포함되지 않은 정점을 연결한다면 정점을 최소 신장 트리에 추가 후 새로 추가된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 모든 간선을 추가한다.
- 최소 신장 트리에 V-1 개의 간선을 추가시켰다면 종료, 아니라면 2번과 3번을 반복한다.
시간 복잡도
- $O(ElogE)$

1. Java

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        ArrayList<ArrayList<int[]>> adj = new ArrayList<>(); // a, cost, b
        for (int i = 0; i < n; ++i)
            adj.add(new ArrayList<>());
        for (var c : costs) {
            adj.get(c[0]).add(new int[]{c[2], c[1]});
            adj.get(c[1]).add(new int[]{c[2], c[0]});
        }
        boolean[] isVisited = new boolean[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        isVisited[0] = true;
        for (var e : adj.get(0))
            pq.add(new int[]{e[0], 0, e[1]}); // cost, a, b  
        int ans = 0;
        int cnt = 0;
        while (cnt < n - 1) {
            var cur = pq.poll();
            if (isVisited[cur[2]]) continue;
            isVisited[cur[2]] = true;
            ans += cur[0];
            ++cnt;
            for (var e : adj.get(cur[2])) {
                if (!isVisited[e[1]])
                    pq.add(new int[]{e[0], cur[2], e[1]});
            }
        }
        return ans;
    }
}

2. C++

#include <string>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

vector<pair<int, int>> adj[104]; 
bool isVisited[104]; 
priority_queue<tuple<int, int, int>,
            vector<tuple<int, int, int>>,
            greater<tuple<int, int, int>>> pq; // cost, vertex a, vertex b

int solution(int n, vector<vector<int>> costs) {
    int e = costs.size();
    for (int i = 0; i < e; ++i) {
        adj[costs[i][0]].push_back({costs[i][2], costs[i][1]});
        adj[costs[i][1]].push_back({costs[i][2], costs[i][0]});
    }
    isVisited[0] = 1;
    for (auto& nxt : adj[0]) 
        pq.push({nxt.first, 0, nxt.second});
    int cnt = 0;
    int ans = 0;
    while (cnt < n - 1) {
        auto [cost, a, b] = pq.top(); pq.pop();
        if (isVisited[b]) continue;
        isVisited[b] = true;
        ans += cost;
        ++cnt;
        for (auto& e : adj[b]) { 
            if (!isVisited[e.second])
                pq.push({e.first, b, e.second});
        }
    }
    return ans;
}