그래프와 트리, DFS, Binary tree

인접행렬로 자식노드 구하기

#include <iostream>
using namespace std;
int arr[5][5] = {0, 1, 1, 0, 0,
    0, 0, 0, 1, 1,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0
};
int main()
{
    int x;
    cin >> x;
    for(int i=0; i<5; i++)
    {
        if(arr[x][i] == 1)
            cout << i << ' ';
    }
    return 0;
}

인접행렬로 부모노드 구하기

#include <iostream>
using namespace std;
int arr[5][5] = {0, 1, 1, 0, 0,
    0, 0, 0, 1, 1,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0
};
int main()
{
    int x, flag = 0;
    cin >> x;
    for(int i=0; i<5; i++)
    {
        if(arr[i][x] == 1)
        {
            flag = 1;
            cout << i << ' ';
            
        }
    }
    if(flag == 0)
        cout << "없음";
    return 0;
}

 

트리는 한 노드가 다른 노드와 같은 노드를 가리키면 트리가 아니다. 또한 싸이클이 없어야 한다.

 

자식 노드에 해당하는 알파벳 출력하기

#include <iostream>
using namespace std;
int arr[5][5] = {0, 1, 1, 0, 0,
    0, 0, 0, 1, 1,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0
};
char name[6] = "ATKCB";
int main()
{
    int x;
    cin >> x;
    for(int i=0; i<5; i++)
    {
        if(arr[x][i] == 1)
        {
            cout << name[i] << ' ';
        }
    }
    return 0;
}

숫자 하나 입력 후, 자식의 수 출력

#include <iostream>
using namespace std;
int map[5][5] = {
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0,
    0, 1, 0, 0, 1,
    1, 0, 1, 0, 0
};
char word[6] = "CKBAT";
int main()
{
    int k, cnt = 0;
    cin >> k;
    for(int i=0; i<5; i++)
    {
        if(map[k][i] == 1)
            cnt++;
    }
    
    cout << cnt;
    return 0;
}

자신의 형제 노드 찾기

#include <iostream>
using namespace std;
int arr[8][8] = {
    0, 1, 1, 1, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 1, 1, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0
}, num[8] = {3, 4, 2, 3, 4, 2, 5, 9};
void find_brother(int parent, int child)
{
    for(int i=0; i<8; i++)
    {
        if(arr[parent][i] == 1 && i != child)
            cout << num[i] << ' ';
    }
}
int main()
{
    int x;
    cin >> x;
    for(int i=0; i<8; i++)
    {

        if(arr[i][x] == 1)
        {
            find_brother(i, x);
        }
        
    }
    return 0;
}

dfs로 트리 탐색하기

#include <iostream>
using namespace std;
int map[6][6] = {
    0, 1, 1, 1, 0, 0,
    0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 1,
    
}, num[6] = {3, 2, 4, 5, 2, 4};
void run(int index)
{
    cout << num[index];
    for(int i=0; i<6; i++)
    {
        if(map[index][i] == 1)
            run(i);
    }
    
}
int main()
{
    run(0);
    return 0;
}

binary tree - 탐색

#include <iostream>
using namespace std;
char arr[10] = " ABC  DE";
void run(int now)
{
    if(now >= 10) return;
    if(arr[now] == ' ' || arr[now] == 0) return;
    cout << arr[now] << ' ' ;
    run(now* 2);
    run(now* 2 + 1);
}
int main()
{
    run(1);
    return 0;
}