[백준 22856번] 트리 순회 (C++)

문제링크 : https://www.acmicpc.net/problem/22856

22856번: 트리 순회

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, result=-1;
vector<int>v[100001];


void inorder(int node, bool flag)
{
    if(node==-1) return;

    int left = v[node][0];
    int right = v[node][1];

    result++;
    inorder(left, 0);

    if(flag) inorder(right, 1); 
    else
    {
        result++; //왼쪽은 왕복이동
        inorder(right, 0); 
    }
    
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back(b);
        v[a].push_back(c);
    }

    inorder(1, 1); 
    cout <<result;
    
    return 0;
}

 

중위순회에 이동횟수를 카운팅하는 문제이다.

단순 카운팅이 아니라 고려해주어야 할 부분이 있는데, 왼쪽으로 가는지 오른쪽으로 가는지에 대해 확인을 해야한다.

보통 이동을 하게되면 내려갔다 다시 올라오느라 왕복으로 이동이 발생하는데, 마지막 노드가 있는 맨 우측으로 이동하는 경우에는 내려갔다 다시 올라올 필요가 없으므로 편도로만 이동이 발생하게 된다.

오른쪽으로 이동하는지, 왼쪽으로 이동하는지 확인을 위해 재귀문에서 체크용 bool 변수를 같이 넘겨준다.

 

처음에는 기본적으로 현 루트에 대해 왼쪽 하나 오른쪽으로 하나가 이동한다.

그리고 매 이동마다 기본적인 카운팅을 1개 해준다.

해당 문제에서 왼쪽에서 이동하는 경우는 flag가 0으로, 오른쪽에서 이동하는 경우는 flag를 1로 설정해준다.

왼쪽으로 이동했을 때 또 해당 값에 대해 왼쪽, 오른쪽으로 나눠서 이동하게 되는데 해당 오른쪽에 대해서는 맨 처음 시작이 왼쪽이므로 flag를 0으로 설정해준다.

또한 트리의 왼쪽 부분은 갔다가 다른값으로 다시 이동하기 위한 왕복이동이 발생하기에 result를 추가로 카운팅해준다.

 

이제 오른쪽의 경우는 오른쪽에서 왼쪽으로 가는 경우는 또 다시 이동해야 하므로 왕복이동이 필요하다.

마지막 노드는 맨 오른쪽에 위치하므로 오른쪽에서 해당 값이 위치한 오른쪽으로 계속 가는 경우는 왕복이 아닌 편도이다.

 

따라서 기본적으로 루트에서 왼쪽값들은 전부 왕복이동이고, 루트에서 오른쪽 값중 왼쪽으로 이동하는 경우만 왕복이동, 이외에는 한번만 이동하는 것을 알 수 있다.

 

결과값을 담을 result의 기본값이 -1인데, 이는 맨처음 시작값인 루트인 경우에도 카운팅을 하므로 해당 경우를 빼주기 위함이다.