Binary tree, dfs(중복 제거) 최단 경로 탐색,

Binary tree 순회

#include <iostream>
using namespace std;
char arr[20] = " TBKRU";

void run(int now)
{
    if(now > 20 ) return;
    if(arr[now] == ' ' || arr[now] == 0) return;
    cout << arr[now] << ' ' ;
    run(now*2);
    run(now*2 + 1);
}
int main()
{
    run(1);
    return 0;
}

Graph 탐색 ( 중복 없이)

#include <iostream>
using namespace std;
int map[6][6] = {
    0, 1, 0, 1, 0, 0,
    0, 0, 1, 0, 0, 0,
    1, 0, 0, 0, 1, 1,
    0, 0, 1, 0, 0, 1,
    0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0
}, name[6] = {5, 7, 1, 9, 4, 2}, used[6];

void run(int now)
{
    cout << name[now] << ' ';
    for(int i=0; i<6; i++)
    {
        if(map[now][i] != 1) continue;
        if(used[i] == 1) continue;
        used[i] = 1;
        run(i);
    }
}
int main()
{
    used[0] = 1;
    run(0);
    return 0;
}

 

dfs 탐색은 노드 탐색과 경로 탐색 두가지로 나뉜다. 노드 탐색은 중복을 체크한 것을 그대로 두고

경로 탐색은 중복 체크를 계속 초기화 해준다.

 

그래프 모든 경로 탐색해서 최소 비용 구하기

#include <iostream>
using namespace std;
int map[4][4] ={
    0, 5, 15, 0,
    3, 0, 0, 4,
    0, 0, 0, 9,
    1, 0, 7, 0
}, start, en, short_len = 21e8, used[4];
char name[5] = "ASKB";

void run(int sum, int now)
{
    if(now == en)
    {
        if(short_len > sum)
            short_len = sum;
        return;
    }
    for(int i=0; i<4; i++)
    {
        if(map[now][i] == 0) continue;
        if(used[i] == 1) continue;
        used[i] = 1;
        run(sum+map[now][i], i);
        used[i] = 0;
    }
}
int main()
{
    cin >> start >> en;
    used[start] = 1;
    run(0, start);
    cout << short_len;
    return 0;
}

 

자식 노드가 2개이면 2진트리 사용하면 편함 그러나 이외의 경우 인접 행렬이나 인접리스트로 해야 한다.

 

현재 위치와 현재까지의 경로값 출력하기

#include <iostream>
using namespace std;
int arr[20] = {0, 5, 3, 7, 2, 4, 0, 1, 0, 0, 0, 0, 0, 0, 9};

void run(int now, int sum)
{
    if(now > 20) return;
    if(arr[now] == 0) return;
    
    cout << arr[now] << '(' << sum+ arr[now] << ')' << '\n';
    run(now*2, sum + arr[now]);
    run(now*2 + 1, sum+ arr[now]);
}
int main()
{
    run(1, 0);
    return 0;
}