백준 22856번 트리 순회 문제풀이 c++

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

22856번: 트리 순회

 

문제 해석

쉽게 말해 중위순회를 하면서 이동 횟수를 출력하는게 문제에서 요구하는것이다.

이 문제는 항상 노드가 1인 이진 트리의 형태를 갖기 때문에 이동 횟수는 다음과 같은 식을 만족한다.

이동횟수는 1을 제외한 모든 노드의 수 * 2에서 1을 제외한 오른쪽 노드 수를 뺀 것이다.

다시 말해 윗 그림과 같은 예시에서는 1을 제외한 모든 노드의 수는 2,3,4,5,6,7로 6개 이고

6*2=12이다 또 1을제외한 오른쪽노드의 개수는 3과 7로 2개이다. 따라서 답은 12-2=10이다.

 

코드

기본 중위 순회 코드는 다음과 같다.

void inorder(int node){
    if(node==-1)
    {
        return;
    }
    int left=tree[node][0];
    int right=tree[node][1];
    inorder(left);
    cout<<node<<" ";
    inorder(right);
    return;
}

여기서 1제외 전체 노드수 루트에서 오른쪽에 있는 노드수를 따로 세주어야 하기때문에 윗 코드에서 조금만 수정하면 된다.

그렇게 수정한 전체 코드는 다음과 같다. 

#include <iostream>
using namespace std;
void inorder(int node,bool flag);
int tree[100001][2];
int all_sub_tree_cnt=-1;
int right_sub_tree_cnt=-1;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        tree[a][0]=b;
        tree[a][1]=c;
    }
    inorder(1,1);
    int ans=2*all_sub_tree_cnt-right_sub_tree_cnt;
    cout<<ans;
}
void inorder(int node,bool flag){
    if(node==-1)
    {
        return;
    }
    int left=tree[node][0];
    int right=tree[node][1];
    all_sub_tree_cnt++;
    inorder(left,0);
    if(flag==1)
    {
        right_sub_tree_cnt++;
        inorder(right,1);
    }
    else
    {
        inorder(right,0);
    }
    return;
}

루트에서 오른쪽으로 갔을때를 알기위해 flag라는 bool타입 변수를 하나 추가했다.

그리고 변수 이름을 노드 갯수라고해도 생각해도되고 서브트리 개수라고 생각해도 되기때문에 저렇게 지었다.