[알고리즘] 트리에서의 BFS, DFS, 이진 트리에서의 순회

[바킹독님 블로그 정리 글입니다!]

[실전 알고리즘] 0x19강 - 트리

 

트리의 기본적인 특성부터 알고 가자면, 트리의 정의는 무방향이면서 사이클이 없는 연결 그래프이다. V개의 정점에 대해 V-1개의 간선을 가지는 사이클이 없는 연결 그래프라고 생각하면 된다.

 

트리에서의 BFS는 그래프의 BFS와는 조금 다른 의미를 가진다. 그래프의 BFS는 특정 정점에서 연결된 점을 찾는 용도로도 많이 사용되었는데, 트리는 연결 그래프이므로 방문 순서와 부모 배열, depth 배열을 채울 수 있다는 것에 의미를 둬야 한다. 

 

트리의 BFS의 구현은 그래프나 배열에서의 탐색과는 조금 다르다. 루트가 아닌 아무 정점에 대해 BFS를 생각해 보면 인접한 정점 중 자신의 부모를 제외하고는 전부 자신의 자식이라 당연히 방문하지 않은 상태가 될 테고 따라서 자신의 자식을 전부 큐에 넣어주기만 하면 된다. 즉, visited 배열로 방문을 체크할 필요가 없다!

 

가장 일반적인 트리에서의 BFS 코드는 다음과 같다. 부모 배열을 채우면서 순회하게 된다.

vector<int> adj[10];
int p[10];
void bfs(int root)
{
    queue<int> q;
    q.push(root);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        cout << cur << '\n';
        for(int next : aj[cur]{
            if(p[cur] == next) continue;
            q.push(next);
            p[next] = cur;
        })
    }
}

각 정점의 부모 번호를 배열 p에 저장하고, 루트의 부모는 자연스럽게 0이 된다. 그래프의 BFS와는 방문 체크를 하지 않고, 부모만 체크하면 된다는 차이점이 있다. 이 코드에서 depth도 전부 계산할 수 있다. 자식의 depth는 부모의 depth+1 임을 이용하면 된다.

vector<int> adj[10];
int p[10];
int depth[10];
void bfs(int root)
{
    queue<int> q;
    q.push(root);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        cout << cur << '\n';
        for (int next : aj[cur] {
                 if (p[cur] == next)
                     continue;
                 q.push(next);
                 p[next] = cur;
                 depth[next] = depth[cur] + 1;
             })
    }
}

 

큐를 스택으로 바꿔주면 DFS도 똑같이 구현이 가능하다. 대신 DFS는 재귀로 구현하는 편이 더 효율적일 수 있고 부모 배열을 쉽게 채울 수 있다는 장점이 있다.

vector<int> adj[10];
int p[10];
int depth[10];

void dfs(int cur)
{
    cout << cur << '\n';
    for (int next : adj[cur])
    {
        if (p[cur] == next)
            continue;
        p[next] = cur;
        depth[next] = depth[cur] + 1;
        dfs(next, cur);
    }
}

 

부모 배열이나 depth 배열을 저장할 필요가 없고 단순 순회만 해도 된다면 파라미터로 parent를 사용하는 재귀 구조가 정말 간단하다. 가장 간단한 DFS, BFS는 해당 방식을 사용하면 된다.

vector<int> adj[10];
void dfs(int cur, int par){
    cout << cur << '\n';
    for(int next : adj[cur]){
        if(par==next) continue;
        dfs(next, cur);
    }
}

---

이진 트리는 트리나 그래프와 동일한 방식으로 표현할 수 있지만 왼쪽, 오른쪽 자식을 구분할 수 없다. 따라서 인접 리스트 대신 구조체나 클래스를 만드는 방식이 더 좋다. 

그런데 구조체나 클래스는 매 번 만들기 번거로워서 왼쪽 자식, 오른쪽 자식을 각각 저장하는 lc, rc 배열을 만들어서 저장하는 방식도 좋다. parent 배열은 사용해도 되고 안 해도 되지만 만들어서 채울 줄은 알아야 한다.

 

이진트리에서의 순회는 네 가지로 나뉜다. 하나씩 알아보자!

레벨 순회

높이 순으로 방문하는 순회이다. 루트에서 BFS를 돌리면 된다. 이진트리를 lc, rc로 구현해서 코드가 조금 다르긴 한데 더 간단하다. 위의 그래프에서 보면 1, 2, 3, 4, 5, 6, 7, 8 순서로 방문한다.

int lc[9];
int rc[9];

void bfs()
{
    // root = 1
    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        cout << cur << '\n';
        if (lc[cur])
            q.push(lc[cur]);
        if (rc[cur])
            q.push(rc[cur]);
    }
}

 

전위 순회

전위 순회는 다음과 같이 작동한다.

1. 현재 정점을방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

알고리즘 자체가 재귀적이라 재귀로 구현하면 될 것 같다. 방문 순서는 1, 2, 4, 5, 8, 3, 6, 7 이 된다. 전위 순회는 사실 DFS와 방문 순서가 동일하다. 구현도 똑같이 재귀로 하면 정말 쉽다!

int lc[9];
int rc[9];

void preorder(int cur)
{
    cout << cur << '\n';
    if (lc[cur])
        preorder(lc[cur]);
    if (rc[cur])
        preorder(rc[cur]);
}

중위 순회

중위 순회는 왼쪽 서브트리 -> 나 -> 오른쪽 서브트리 순으로 처리하는 순회 방법이다. 방문 순서는 4, 2, 5, 8, 1, 6, 3, 7 이 된다. 이진 탐색 트리였다면 자연스럽게 크기 순으로 방문하게 된다. 제일 왼쪽에 있는 것부터 방문하기 때문이다. 구현은 preorder와 거의 똑같다.

int lc[9];
int rc[9];

void inorder(int cur)
{
    if (lc[cur])
        inorder(lc[cur]);
    cout << cur << '\n';
    if (rc[cur])
        inorder(rc[cur]);
}

후위 순회

후위 순회는 왼쪽 서브트리 -> 오른쪽 서브트리 -> 나 순서로 방문한다. 4, 8, 5, 2, 6, 7, 3, 1 순으로 방문하게 된다.

int lc[9];
int rc[9];

void postorder(int cur)
{
    if (lc[cur])
        postorder(lc[cur]);
    if (rc[cur])
        postorder(rc[cur]);
    cout << cur << '\n';
}

 

https://www.acmicpc.net/problem/11725

https://www.acmicpc.net/problem/1991

 

위의 두 문제만 간단하게 풀어보면 좋을 것 같다. 모두 트리의 매우 기초적인 입출력 방식과 순회 방식을 다루고 있다. 두 번째 문제만 좀 조심하면 될 것 같은데, 문자를 정수형으로 다루는 것까지는 떠올리기 쉽다. 하지만 lc, rc의 값이 0이 되면 자식이 없는 것과 똑같이  처리하기에 A를 0이 아니라 1로 두기 위해 l-'A'+1 이런 식으로 바꿔야 한다는 점만 조심하자.

정답은 아래 링크에!

https://github.com/jjj5306/BOJ/blob/main/BOJ/Tree1991.cpp

https://github.com/jjj5306/BOJ/blob/main/BOJ/Tree11725.cpp