백준 22856 트리순회 C++

문제

노드가 N$N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자.

순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다.

유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다.

1. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.
2. 그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 오른쪽 자식 노드로 이동한다.
3. 그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.
4. 그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.
5. 유사 중위 순회를 종료할 때까지 1 ~ 4를 반복한다.

위 그림에 있는 트리에서 중위 순회를 한다면 4→2→5→1→6→3→7$4 \rightarrow 2 \rightarrow 5 \rightarrow 1 \rightarrow 6 \rightarrow 3 \rightarrow 7$ 순으로 순회를 한다.

따라서, 유사 중위 순회의 끝은 노드 7이 된다.

유사 중위 순회는 위 그림과 같이 루트인 노드 1$1$에서 시작하여 노드 7$7$에서 끝나고 1→2→4→2→5→2→1→3→6→3→7$1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 7$ 이와 같은 순서로 순회를 진행한다. 유사 중위 순회를 진행하면서 총 10번 이동하였다.

여기서 이동이라는 것은 하나의 노드에서 다른 노드로 한번 움직이는 것을 의미한다. 예를 들면, 노드 1에서 노드 2로 가는 것을 한번 이동하였다고 한다.

유사 중위 순회를 하면서 이동한 횟수를 구하려고 한다.

 

---

뭔가 트리 순회 중에서 inorder(중위순회)에 조금 부가적인 정보를 넣은 것 같은 문제였다.

중위 순회를 간단히 하면,

• 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순으로 트리를 방문하는 것이다.
• 밑의 그림에 자세히 왼쪽 자식 노드 D부터 시작해서 트리의 중위 순회를 하면 DBFEGAC가 나온다.

중위순회

 

이 코드는 중위순회를 대략적으로 구현한 것이다. 트리의 순회는 재귀적으로 방문하는 성질이 있다.

void inorder(Node *root){
    if(root == nullptr){
        return;
    }
    inorder(root->left);
    cout << root->data;
    inorder(root->right);
}

이제 문제에서 주어진 조건을 살펴보자.

1. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.
2. 그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 오른쪽 자식 노드로 이동한다.
3. 그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.
4. 그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.
5. 유사 중위 순회를 종료할 때까지 1 ~ 4를 반복한다.

유사 중위 순회의 끝은 중위 순회 시 , 마지막 노드이다.

그래서, 중위순회를 먼저 해서, 중위 순회의 끝 노드를 먼저 알아내야 한다고 생각했다.

 

먼저 이진 트리의 구조체를 정의했다.

다루는 데이터가 숫자이므로, int형을 왼쪽 자식 트리, 오른쪽 자식트리의 주소를 담는 포인터를 선언했다.

struct node{
    int data;
    node *left = NULL;
    node *right = NULL;
};

모든 자식의 주소를 NULL로 초기화했다.

노드의 부모를 관리하는 배열, 트리를 나타내는 벡터, 방문 처리 배열을 선언하였다.

int n;
int Counter = 0;
 
int start_data,end_data;
vector<node> tree(100001);
bool visited[100001];
int parents[100001];

먼저 정점과, 정점의 왼쪽 자식, 정점의 오른쪽 자식을 입력받았다. (-1인 경우 자식 없음)

void init(){
    cin >> n;
    for(int i = 0;i<n;i++){
        int rootnode;
        int leftnode;
        int rightnode;
        cin >> rootnode >> leftnode >> rightnode;
        tree[rootnode].data = rootnode;
 
        if(leftnode != -1){
            tree[rootnode].left = &tree[leftnode];
            parents[leftnode] = rootnode;
        }
        if(rightnode != -1){
            tree[rootnode].right = &tree[rightnode];
            parents[rightnode] = rootnode;
        }
    }
 
}

그 후, 중위 순회로 중위 순회의 끝 노드를 구하고, 문제에서 단계별로 코드를 작성했다.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
 
struct node{
    int data;
    node *left = NULL;
    node *right = NULL;
};
 
 
int n;
int Counter = 0;
 
int start_data,end_data;
vector<node> tree(100001);
bool visited[100001];
int parents[100001];
 
void init(){
    cin >> n;
    for(int i = 0;i<n;i++){
        int rootnode;
        int leftnode;
        int rightnode;
        cin >> rootnode >> leftnode >> rightnode;
        tree[rootnode].data = rootnode;
 
        if(leftnode != -1){
            tree[rootnode].left = &tree[leftnode];
            parents[leftnode] = rootnode;
        }
        if(rightnode != -1){
            tree[rootnode].right = &tree[rightnode];
            parents[rightnode] = rootnode;
        }
    }
 
}
 
 
void inorder(node *currentnode){
 
    if(currentnode == NULL){
        return;
    }
    inorder(currentnode->left);
    end_data = currentnode->data;
    inorder(currentnode->right);
}
 
void different_inorder(node *currentnode){
   
    //현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.
    if(currentnode->left != NULL && visited[currentnode->left->data] == false){
        visited[currentnode->left->data] = true;\
        Counter += 1;
        different_inorder(currentnode->left);
    }
    //그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 
    //오른쪽 자식 노드로 이동한다.
    else if(currentnode->right != NULL && visited[currentnode->right->data] == false){
        visited[currentnode->right->data] = true;
        Counter += 1;
        different_inorder(currentnode->right);
    }
    //그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.
    else if(currentnode->data == end_data){
       return;
    }
    //그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.
    else{
        Counter+=1;
        different_inorder(&tree[parents[currentnode->data]]);
    }
 
}
 
 
 
 
int main(void){
    init();
    parents[1] = 1;
    inorder(&tree[1]);
    different_inorder(&tree[1]);
    cout << Counter;
}