해커를 꿈꾸는 개발자

[C++11] std::bind, std::placeholders 사용법

std::bind란?

함수 템플릿 바인드는 함수에 대한 전달 호출 wrapper를 생성합니다. 전달 인자를 설정할 수 있는 함수 포인터라고 보시면 됩니다. 
 

std::bind 사용 방법

template< class F, class... Args >
/*unspecified*/ std::bind( F&& f, Args&&... args );
 
f - 일부 인수에 바인딩되는 호출 가능한 객체입니다.(함수 객체, 함수에 대한 포인터, 함수에 대한 참조, 멤버 함수에 대한 포인터 또는 데이터 멤버에 대한 포인터)
이
args - 바인드할 전달인자 목록입니다. 바인딩되지 않은 인수는 namespace std::placeholders의 자리 표시자 _1, _2, _3...으로 대체될 수 있습니다. 
 

std::placeholder 이란?

보통 std::bind와 같이 많이 쓰이며, 함수의 인자를 받을 수 있도록 해줍니다. 
std::placeholders::_1, std::placeholders::_2, ..., std::placeholders::_N 형식으로 사용됩니다. 
 

std::bind, std::placeholder의 header 파일

#include <functional>
 

std::bind, std::placeholder의 사용 예제

#include <iostream>
#include <functional>


void add(int n1, int n2) {
    std::cout << "n1 = " << n1 << ", n2 = " <<  n2 << std::endl;
    std::cout << "add = " << n1 + n2 << std::endl;
}

void sub(int n1, int n2) {
    std::cout << "n1 = " << n1 << ", n2 = " << n2 << std::endl;
    std::cout << "sub = " << n1 - n2 << std::endl;
}

int main() {
    auto f1 = std::bind(add, 100, std::placeholders::_1);
    f1(5); // add(100, 5) 형식으로 호출됩니다.

    auto f2 = std::bind(sub, std::placeholders::_1, std::placeholders::_2);
    f2(10, 7); // sub(10, 7) 형식으로 호출됩니다.

    return 0;
}

참조

https://en.cppreference.com/w/cpp/utility/functional/bind

https://en.cppreference.com/w/cpp/utility/functional/placeholders

알고리즘 : 최소 스패닝 트리(Minimum Spanning Tree) - 크루스칼 알고리즘 구현하기

최소 스패닝 트리는 스패닝 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말합니다. 

최소 스패닝 트리를 만들기 위한 조건은 아래와 같습니다. 

- 본래의 그래피의 모든 노드를 포함해야 합니다. 

- 간선의 가중치의 합이 최소여야 합니다. 

- 모든 노드가 서로 연결되어 있어야 합니다. 

- Cycle이 존재하지 말아야 합니다. 

최소 스패닝 트리를 구하기 위한 대표적인 알고리즘이 2가지가 있습니다. 

첫번째는 크루스칼 알고리즘(Kruskal Algorithm)이며, 두번째는 프림 알고리즘(Prim Algorithm)입니다. 

이번 시간에는 크루스칼 알고리즘에 대해 알아보겠습니다. 

크루스칼 동작 원리

1) 모든 간선들의 가중치를 오름차순으로 정렬합니다 

2) 가중치가 가장 작은 간선부터 선택합니다. 

3) 선택한 간선이 사이클을 만들지 않는다면, 두 개의 노드를 연결합니다. 

4) 모든 노드를 연결할 때까지 1) ~ 3)의 과정을 반복합니다. 

크루스칼 동작 과정

아래와 같은 그래프가 있다고 가정합니다. 

노드는 1부터 7까지 있고, 모든 노드가 연결되지 않은 독립된 상태입니다. 

노드 1과 노드 2의 간선의 가중치는 3입니다. 

다른 모든 연결된 간선도 가중치를 가지고 있습니다. 

이 그래프를 크루스칼 알고리즘을 이용하여, 최소 스패닝 트리를 찾아보도록 하겠습니다. 

먼저 Parent 배열을 만들고, 각 주소에 각 노드로 초기화합니다. Parent 배열은 각 연결된 부분의 가장 상단의 부모가 공통인지를 검사하여, 각 노드가 연결되어 있는지, 독립하여 존재하는지 검사하기 위해 사용됩니다. (즉, 두 노드를 연결할 때, Cycle이 발생하지 않도록 검사하기 위해 필요합니다.)

모든 간선은 가중치의 값을 오름차순으로 정렬하도록 합니다. 

간선의 가중치가 가장 낮은 {2} 와 {3}을 연결시킵니다. 

To의 Parent는 From의 최 상위의 부모로 지정합니다. 

그러면 [2]에는 From인 3이 부모가 됩니다. 

이러한 과정을 반복합니다. 

노드 1과 노드 2를 연결하면 사이클이 발생하여 연결되지 못합니다. 또한 노드 5와 노드 6, 노드 5와 노드 4도 동일하게 사이클을 발생시키기 때문에 연결되지 못합니다. 

크루스칼 알고리즘을 동작시키면, 아래와 같이 최소 스패닝 트리가 구해지고, 

최소 비용의 값은 14가 됩니다. 

크루스칼 구현

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <queue>
#include <stack>
#include <list>
using namespace std;


// 간선의 정보를 나타낼 구조체를 정의합니다. 
struct Edge {
    int from, to, weight;
    Edge(int f, int t, int w) {
        from = f;
        to = t;
        weight = w;
    }
};

vector<Edge> v; // 모든 간선의 정보를 담음
int N; // 노드의 수
int M; // 간선의 수 
int result = 0; // 최소 스패닝 트리의 모든 가중치의 합
int parent[100001]; // Parent 배열

// 입력정보
void inputData() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int f, t, w;
        cin >> f >> t >> w;
        v.push_back(Edge(f, t, w));
    }
}

void printV() {
    for (int i = 0; i < M; i++) {
        cout << v[i].from << " " << v[i].to << " => " << v[i].weight << '\n';
    }
}

// 가중치 오름차순으로 정렬하기 위한 compare 함수
bool comp(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

// 최상위의 부모노드를 구합니다. 
int getParent(int x) {
    if (x == parent[x]) return x;
    else
        return parent[x] = getParent(parent[x]);
}

// 두 노드를 연결합니다. 
void Union(int x, int y)
{
    x = getParent(x);
    y = getParent(y);

    if (x == y) return ; // 두 노드의 최상위 부모가 동일한지 검사합니다.
    parent[y] = x;
}

// 사이클을 이루는지 확인합니다.
bool isCycle(int x, int y) {
    x = getParent(x);
    y = getParent(y);

    if (x == y)
        return true;

    return false; 
}


void solve() {
    sort(v.begin(), v.end(), comp); // 가중치 오름차순으로 간선을 정렬합니다. 
    
    for (int i = 1; i <= N; i++) parent[i] = i; // 우선 parent 배열에 각 노드로 초기합니다.

	// 두 노드를 연결하였을 때, 사이클을 이루지 않는다면, 두 노드를 연결시킵니다. 
    for (int i = 0; i < v.size(); i++) {
        if (isCycle(v[i].from, v[i].to) == false) {
           // cout << " Union : " << v[i].from << " " << v[i].to << " w : " << v[i].weight << '\n';
            Union(v[i].from, v[i].to);

            result += v[i].weight; // 가중치의 모든 합을 구합니다. 
        }
    }
}

void printData() {
    cout << result;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    inputData();
    solve();
    printData();

    return 0;
}