[BOJ] 백준 1922 네트워크 연결 / 최소 신장 트리(MST), 크루스칼

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

컴퓨터를 노드로, 선 연결을 간선으로 보고 주어진 그래프에서 최소 신장 트리(MST)의 합을 구하는 문제였다.

틀은 바뀌었지만 1197번 최소 스패닝 트리 와 그냥 동일하게 풀리는 문제이다.

크루스칼 알고리즘/프림 알고리즘 두 가지 방법으로 풀 수 있다.

 

이 문제는 크루스칼 알고리즘으로 풀이했다.

 

 

💭 풀이 과정

 

 

 

작성 언어: C++

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

class Line {
public:
    int start, dest, weight;
    
    Line(int start, int dest, int weight) {
        this->start = start;
        this->dest = dest;
        this->weight = weight;
    }
};

const int MAX = 1001;
int com_cnt, line_cnt;
vector<Line> lines;
int parent[MAX] = {0, };
int depth[MAX] = {0, };

// 초기 설정
void initialize() {
    for (int i = 0; i <= com_cnt; ++i) {
        parent[i] = i;
        depth[i] = 1;
    }
}

// 가중치에 따른 오름차순 정렬
bool compare(const Line &l1, const Line &l2) {
    return l1.weight < l2.weight;
}

// root 노드 찾기
int findRoot(int node) {
    if (node == parent[node])   return node;
    return parent[node] = findRoot(parent[node]);
}

// 트리 합병
void mergeTree(const int node1, const int node2) {
    if (depth[node1] < depth[node2]) {
        depth[node2] += depth[node1];
        depth[node1] = 0;
        parent[node1] = node2;
    }else {
        depth[node1] += depth[node2];
        depth[node2] = 0;
        parent[node2] = node1;
    }
}


int main() {
    int result = 0;
    cin >> com_cnt;
    cin >> line_cnt;
    for (int i = 0; i < line_cnt; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        lines.push_back(Line(a, b, c));
    }
    
    // 가중치 기준 오름차순 정렬
    sort(lines.begin(), lines.end(), compare);
    
    // parent, depth 배열 초기화
    initialize();
    
    for (int i = 0; i < line_cnt; ++i) {
        int start_root = findRoot(lines[i].start);
        int dest_root = findRoot(lines[i].dest);
        
        if (start_root != dest_root) {
            result += lines[i].weight;
            mergeTree(start_root, dest_root);
        }
    }
    
    cout << result << endl;
    
    return 0;
}

 

 

🏆 배운 점

 

 

코딩 테스트에 어려운 문항들 중 꼭 한 문제 씩은 최단 경로 탐색 또는 최소 신장 트리(MST)와 관련된 문제가 나오곤 했다.

알고리즘 수업 과제로 Kruskal, Prim 알고리즘을 접하면서 백준으로 연습하겠다는 생각으로 풀어보았다.

DFS, BFS 문제를 풀었던 것처럼 이 유형이 익숙해질 때까지 다양하게 풀어봐야겠다!!!