Union Find, MST, BST

Union Find 

getParent(char ch) : 부모를 찾기 위한 함수

setGroup(char a, char b) : a와 b를 같은 그룹으로 묶기

 

그룹으로 묶고 현재 몇개의 그룹이 있는지 출력하기

#include <iostream>
using namespace std;
int vect[200], cnt = 6;
char getBoss(char ch)
{
    if(vect[ch] == 0) return ch;
    
    char ret = getBoss(vect[ch]);
    
    vect[ch] = ret;
    return ret;
}

void setGroup(char a, char b)
{
    char aBoss = getBoss(a);
    char bBoss = getBoss(b);
    if(aBoss == bBoss) return;
    vect[bBoss] = aBoss;
    cnt--;
}
int main()
{

    setGroup('a', 'e');
    setGroup('f', 'e');
    setGroup('c', 'e');
    setGroup('c', 'a');
    setGroup('b', 'd');
    setGroup('d', 'b');
    cout << cnt;
    return 0;
}

그래프에서 싸이클 탐색

#include <iostream>
using namespace std;
int vect[200], cnt = 6, flag = 0;
char getBoss(char ch)
{
    if(vect[ch] == 0) return ch;
    
    char ret = getBoss(vect[ch]);
    
    vect[ch] = ret;
    return ret;
}

void setGroup(char a, char b)
{
    char aBoss = getBoss(a);
    char bBoss = getBoss(b);
    if(aBoss == bBoss) return;
    vect[bBoss] = aBoss;
}
int main()
{
    char list[4][3] = {
        "ab",
        "be",
        "cb",
        "ae"
    };
    for(int i=0; i<4; i++)
    {
        if(getBoss(list[i][0]) == getBoss(list[i][1]))
        {
            flag = 1;
            break;
        }
        else
        {
            setGroup(list[i][0], list[i][1]);
        }
    }
    
    if(flag == 1)
        cout << "싸이클 발견";
    else
        cout << "싸이클 미발견";
    return 0;
}

 

vector와 &(레퍼런스) 공부하기

MST

먼저 간선을 Cost가 작은 순으로 정렬한 뒤, Union & Find를 사용하여 그룹을 짓는다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int vect[100];
struct Node
{
    char start, end;
    int cost;
};
bool compare(Node a, Node b)
{
    return a.cost < b.cost;
}
vector<Node> mst = {
    {'A', 'B', 5},
    {'A', 'C', 3},
    {'A', 'D', 2},
    {'A', 'E', 6},
    {'B', 'C', 7},
    {'B', 'E', 8},
    {'C', 'D', 4},
    {'C', 'E', 2},
};

char getParent(char ch)
{
    if(vect[ch] == 0 ) return ch;
    char ref = getParent(vect[ch]);
    vect[ch] = ref;
    
    return ref;
}
void Union(char a, char b)
{
    char aBoss = getParent(a);
    char bBoss = getParent(b);
    if(aBoss == bBoss) return;
    vect[bBoss] = aBoss;
}
int main()
{
    int totalCost = 0, checking = 0;
    sort(mst.begin(), mst.end(), compare);
    for(int i=0; i<mst.size(); i++)
    {
        if(getParent(mst[i].start) != getParent(mst[i].end))
        {
            totalCost += mst[i].cost;
            checking++;
            Union(mst[i].start, mst[i].end);
        }
        if(checking == 4)
            break;
    }
    cout << totalCost;
    return 0;
}

 

BST

BST와 BS의 차이

BS: 정렬된 데이터에서 진행하는 이진 탐색(알고리즘)

BST: 빠른 검색을 위한 자료구조

#include <iostream>
using namespace std;
int num[100];
void insert(int n)
{
    int now = 1;
    while(1)
    {
        if(num[now] == 0)
        {
            num[now] = n;
            return;
        }
        if(num[now] < n)
            now = now * 2 + 1;
        else
            now = now * 2;
    }
}

int find(int n)
{
    int now = 1;
    while(1)
    {
        if(now > 100) return 0;
        if(num[now] == n) return 1;
        if(num[now] == 0) return 0;
        
        if(num[now] < n)
            now = now * 2 + 1;
        else
            now = now * 2;
    }
    
    return 0;
}
int main()
{
    insert(4);
    insert(2);
    insert(6);
    insert(9);
    insert(11);
    insert(5);
    
    if(find(5) == 1)
        cout << "find";
    else
        cout << "not find";
    return 0;
    
}