낙서 코딩

개념

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘으로 흔히 여러개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소로 하기 위해 실제로 적용되는 알고리즘이다.

노드 = 정점 = 도시

간선 = 거리 = 비용

일단 모든 노드를 최대한 적은 비용으로 연결 시켜야하기 때문에 간선 정보를 오름차순으로 정렬 한 후 비용이 적은 간선부터 차근차근 그래프에 포함시킨다. 단 이때 사이클을 형성하게 될 경우 간선을 포함하지 않는다.

조건

1. 간선 정보를 오름차순으로 정렬
2. 사이클이 형성되지 않게 연결

사용하기 좋은 경우

1. 모든 노드를 최소 비용으로 연결할 경우
2. 연결되어있는 그룹의 수를 구하는 경우 → 크루스칼 알고리즘으로 다 연결 한 후 최상단 부모의 개수가 그룹의 수이다.

구현 방법

1. 비용, 출발, 도착의 정보를 갖는 노드들을 비용을 기준으로 오름차순 정렬하기

typedef pair<int, int> pii;
for(int i = 0; i < m; i++) { //a: 출발지점, b: 도착지점, c: 비용
        scanf("%d%d%d", &a, &b, &c);
        v.push_back(pair<int, pii>(c, pii(a,b)));
    }
    int p = 0;
    sort(v.begin(), v.end()); //비용 기준으로 정렬

1. 최상단 부모 찾기

int parent[10001];

int findParent(int child) {
    if(parent[child] == 0) {
        return child;
    }
    return parent[child] = findParent(parent[child]);
}

parent 배열의 인덱스는 자기 자신을 나타내고 값은 자신의 부모를 나타낸다. 값이 0일경우 부모가 존재하지 않는 것으로 최상단 노드를 의미하기 때문에 값이 0일때를 찾아서 return 한다.

1. 부모 자식 관계 설정하기, 최소 비용 구하기

int unionSet(pair<int, pii> xy) {
    int xp = findParent(xy.second.first); //출발 지점의 부모 찾기
    int yp = findParent(xy.second.second); //도착 지점의 부모 찾기
    
    if(xp == yp) return xp; //부모가 같으면 이미 연결되어 있는 것이므로 종료
    else { //부모가 다르면 서로 다른 선에 연결되어 있기 때문에 한 쪽의 부모를 다른 쪽 부모에 연결
        cost[xp] += cost[yp] + xy.first; //연결 후 최상단 노드의 비용을 더해줌
        parent[yp] = xp; //한 쪽의 최상단 부모를 다른 쪽 최상단 부모로 설정
    }
    return xp; //새로운 연결선의 최상단 노드
}

부모가 같으면 이미 연결되어있는 상태이고 다르면 서로의 최상단 부모를 연결해준다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;
int n, m, a, b, c, answer;

vector<pair<int, pii>> v;

int parent[10001];
int cost[10001];

int findParent(int child) {
    if(parent[child] == 0) {
        return child;
    }
    return parent[child] = findParent(parent[child]);
}

int unionSet(pair<int, pii> xy) {
    int xp = findParent(xy.second.first);
    int yp = findParent(xy.second.second);
    
    if(xp == yp) return xp;
    else {
        cost[xp] += cost[yp] + xy.first;
        parent[yp] = xp;
    }
    return xp;
}

int main(int argc, const char * argv[]) {
    scanf("%d", &n);scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        v.push_back(pair<int, pii>(c, pii(a,b)));
    }
    int p = 0;
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++) {
        p = unionSet(v[i]);
    }
    answer = cost[p];
    printf("%d", answer);
    
    return 0;
}

시간복잡도

O(logN)