[PCCP] Lv3: 섬 연결하기(42861) 해설

문제

- 문제 링크: 섬 연결하기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

- 노드 개수 N, costs의 길이 E

- 간선을 비용 기준으로 정렬: O(ElogE)

- costs 순회하며 find(), union() 호출: O(E)

- 최종 시간복잡도: O(ElogE)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 상호배타적 집합 정의
class DisjointSet {
private:
    vector<int> parent, rank;
    
public:
    DisjointSet(int size) : parent(size, -1), rank(size, 0) {}
    
    int find(int node) {
        if (parent[node] == -1)
            return node;
        // 경로 압축을 하며 루트 노드 탐색
        return parent[node] = find(parent[node]);
    }
    
    void merge(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        
        if (root1 != root2) {
            // 랭크 기반으로 합치기
            if (rank[root1] > rank[root2]) {
                parent[root2] = root1;
            } else if (rank[root1] < rank[root2]) {
                parent[root1] = root2;
            } else {
                parent[root2] = root1;
                rank[root1]++;
            }
        }
    }
    
    // 같은 집합에 있는지 확인
    bool isCycle(int node1, int node2) { return find(node1) == find(node2); }
};


int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // 비용을 기준으로 간선 정렬
    sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; });
    
    DisjointSet disjointSet(n);
    int totalCost = 0;
    
    for (const auto& edge : costs) {
        int cost = edge[2];
        int node1 = edge[0];
        int node2 = edge[1];
        
        // 사이클 확인 후 없으면 합병
        if (!disjointSet.isCycle(node1, node2)) {
            disjointSet.merge(node1, node2);
            totalCost += cost;
        }
    }
    
    return totalCost;
}

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 노드의 개수

- E: costs의 길이. 간선의 개수

- 간선을 비용 기준으로 정렬: O(ElogE)

- costs를 순회하면서 find(), union()을 호출하기 위한 시간 복잡도는 O(ElogE)

- 최종 시간 복잡도: O(ElogE)

import java.util.Arrays;

class Solution {
    private static int[] parent;
    
    private static int find(int x) {
        // x가 속한 집합의 루트 노드 찾기
        if (parent[x] == x)
            return x;
        // 경로 압축: x의 부모를 루트로 설정
        return parent[x] = find(parent[x]);
    }
    
    private static void union(int x, int y) {
        // 두 집합을 하나의 집합으로 합치기
        int root1 = find(x);
        int root2 = find(y);
        parent[root2] = root1;
    }
    
    public int solution(int n, int[][] costs) {
        // 비용을 기준으로 다리를 오름차순 정렬
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2]));
        
        // parent 배열 초기화
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
        
        int answer = 0; // 최소 신장 트리의 총비용
        int edges = 0; // 연결한 다리의 수
        
        for (int[] edge: costs) {
            // n - 1개의 다리가 연결된 경우 모든 섬이 연결됨
            if (edges == n - 1)
                break;
            // 현재 다리가 연결하는 두 섬이 이미 연결되어 있는지 확인
            if (find(edge[0]) != find(edge[1])) {
                // 두 섬을 하나의 집합으로 연결함
                union(edge[0], edge[1]);
                // 현재 다리의 건설 비용을 총비용에 추가
                answer += edge[2];
                // 사용된 다리의 수 1 증가
                edges++;
            }
        }
        return answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 노드 개수

- E: costs의 길이. 간선의 개수

- 간선을 비용 기준으로 정렬: O(ElogE)

- costs를 순회하면서 find(), union()을 호출하기 위한 시간 복잡도: O(E)

- 최종 시간 복잡도: O(ElogE)

def find(parent, i):
    # 'i'가 속한 집합의 루트 노드 찾기
    if parent[i] == i:
        return i
        
    # 경로 압축: 'i'의 부모를 직접 루트로 설정
    parent[i] = find(parent, parent[i])
    return parent[i]
    
def union(parent, rank, x, y):
    # 랭크를 기준으로 두 집합을 합치기
    xroot = find(parent, x)
    yroot = find(parent, y)
    
    if rank[xroot] < rank[yroot]:
        # 작은 랭크의 트리를 큰 랭크의 트리 아래에 연결
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        # 랭크가 같은 경우, 한 트리를 다른 트리에 붙이고 랭크 증가
        parent[yroot] = xroot
        rank[xroot] += 1
        
def solution(n, costs):
    # 비용을 기준으로 간선을 오름차순 정렬
    costs.sort(key=lambda x: x[2])
    
    # 각 노드의 부모를 추적하는 parent 배열 생성
    parent = [i for i in range(n)]
    
    # 각 노드의 트리의 랭크를 추적하는 rank 배열 생성
    rank = [0] * n
    
    min_cost = 0 # 최소 신장 트리의 총 비용
    edges = 0 # 최소 신장 트리에 포함된 간선의 개수
    
    for edge in costs:
        if edges == n - 1: # n - 1개의 간선이 포함된 경우 중단(최소 신장 트리의 속성)
            break
        
        # 현재 간선의 두 노드가 속한 집합의 루트 찾기
        x = find(parent, edge[0])
        y = find(parent, edge[1])
        
        if x != y:
            # 두 노드가 서로 다른 집합에 속하는 경우, 집합 합치기
            union(parent, rank, x, y)
            # 현재 간선의 비용을 최소 비용에 추가
            min_cost += edge[2]
            # 포함된 간선의 개수 증가
            edges += 1
        
    return min_cost

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: 노드의 개수

- E: costs의 길이. 간선의 개수

- 간선을 비용 기준으로 정렬하기 위한 시간 복잡도: O(ElogE)

- costs를 순회하면서 find(), union() 함수 호출하기 위한 시간복잡도: O(E)

- 최종 시간 복잡도: O(ElogE)

function find(parent, i) {
    // 'i'가 속한 집합의 루트 노드 찾기
    if (parent[i] == i) {
        return i;
    }
    
    // 경로 압축: 'i'의 부모를 직접 루트로 설정
    parent[i] = find(parent, parent[i]);
    return parent[i];
}

function union(parent, rank, x, y) {
    // 랭크를 기준으로 두 집합을 합치기
    const xroot = find(parent, x);
    const yroot = find(parent, y);
    if (rank[xroot] < rank[yroot]) {
        // 작은 랭크의 트리를 큰 랭크의 트리 아래에 연결
        parent[xroot] = yroot;
    } else if (rank[xroot] > rank[yroot]) {
        parent[yroot] = xroot;
    } else {
        // 랭크가 같은 경우, 한 트리를 다른 트리에 붙이고 랭크 증가
        parent[yroot] = xroot;
        rank[xroot] += 1;
    }
}

function solution(n, costs) {
    // 비용을 기준으로 간선을 오름차순 정렬
    costs.sort((a, b) => a[2] - b[2]);
    
    // 각 노드의 부모를 추적하는 parent 배열 생성
    const parent = Array.from({length: n}, (_, i) => i);
    
    // 각 노드의 트리의 랭크를 추적하는 rank 배열 생성
    const rank = Array(n).fill(0);
    
    let minCost = 0; // 최소 신장 트리의 총 비용
    let edges = 0; // 최소 신장 트리에 포함된 간선의 개수
    
    for (const edge of costs) {
        if (edges === n - 1) // n - 1개의 간선이 포함된 경우 중단(최소신장트리의 속성)
            break;
        
        // 현재 간선의 두 노드가 속한 집합의 루트 찾기
        const x = find(parent, edge[0]);
        const y = find(parent, edge[1]);
        
        if (x !== y) {
            // 두 노드가 서로 다르 집합에 속하는 경우, 집합 합치기
            union(parent, rank, x, y);
            
            // 현재 간선의 비율을 최소 비용에 추가
            minCost += edge[2];
            
            // 포함된 간선의 개수 증가
            edges += 1;
        }
    }

    return minCost;
}

solution 2)

import

solution 3)

import