C++ 백준 22856 트리 순회

백준 22856

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

22856번: 트리 순회

풀이 전 나의 생각

노드가 N개인 이진 트리가 주어질 때, 이를 중위 순회와 유사하게 순회하는
유사 중위 순회의 방식으로 순회하며 이동한 거리를 구해야 한다.

 

조건

•  1 ≤ N ≤ 100,000
•  1 ≤ a, b ≤ N

과정

유사 중위 순회의 방식음 다음과 같다.

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

조건을 하나씩 읽어보면서 알 수 있는 사실은 말은 유사 중위 순회지만

실제로 중위 순회를 재귀 방식으로 구현하면 위의 방식과 같이 동작한다는 것을 알 수 있다.

 

따라서 재귀를 사용한 중위 순회 메서드를 만들어 본 경험이 있다면 이를 약간 수정하여

문제를 풀어낼 수 있다.

 

다음으로 문제를 봤을 때 인지해야 하는 중요한 포인트는

순환을 하는 곳과 하지 않는 곳이 나뉘어져 있다는 것이다.

 

그럼 모든 노드가 순환한다고 가정할 때 루트 노드를 제외한 노드 * 2를 해주면 

모든 노드가 순환했을 때의 이동 횟수가 나온다. ex) 7개의 노드 -> (7 - 1) * 2 = 12

 

그럼 전체를 순환했을 때 나온 이동 횟수에 순환하지 않는 노드의 개수를 빼주면

문제에서 구하고자 하는 이동 횟수를 구해낼 수 있다. 

 

중위순회에서 순환하지 않는 부분은 오른쪽 노드에서 오른쪽으로 이동할 때 순환하지 않는다.

 

 

트리의 예시를 보면 1 - 3 - 7은 다른 노드들과 달리 순환하지 않는다.

 

왜냐하면 3 과 7에서 순환을 해버린다면 그거야 말로 순환 사이클 트리가

되버리는 이유도 있고, 중위 순환의 특징이 결국 부모의 노드로 갔다가 오른쪽 노드로 마무리

되기 때문에 이 점을 이용하여 순환하지 않는 노드를 현재 루트 노드의 정점 * 2를 한 수에서

빼준다면 구하고자 하는 모든 이동 횟수를 구해낼 수 있다.

 

1. 탐색할 노드의 정보를 저장해준다.

for (int i = 0; i < N; i++)
	{
		int p, l, r;
		cin >> p >> l >> r;

		parent[p].first = l;
		parent[p].second = r;
	}

 

2. 트리를 유사 중위 순회하며 구하고자 하는 노드의 개수를 구한다.

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

	int left = parent[node].first;
	int right = parent[node].second;

	inorder(left, 0);

	if (flag == 1)
	{
		right_node++;
		inorder(right, 1);
	}
	else
	{
		inorder(right, 0);
	}
}

첫 번째로 구해야 할 것은 루트 노드를 제외한 나머지의 노드인데

이는 처음에 문제에서 N으로 전체 노드의 개수가 주어지니 따로 구할 필요는없다.

 

두 번째로 루트 노드를 기준으로 오른쪽으로 가는 노드의 개수를 구해야 한다.

그럼 루트의 오른쪽으로 가겠다는 표시를 flag = 1로 설정해주고
루트 기준의 오른쪽 노드들을 탐색할 때 마다 right_node를 증가시켜준다.

 

근데 사실 루트 노드를 제외한 노드의 개수는 이전에 말했듯이 N으로 구할 수 있기 때문에

굳이 모든 노드의 순회를 하지 않아도 된다.

 

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

	int right = parent[node].second;

	right_node++;
	inorder(right);
}

이와 같이 정말 루트 노드의 오른쪽 노드들만 구하는 코드를 작성해도

훨씬 더 메모리를 절약하면서 풀 수 있다.

 

중위 순회에 대한 개념을 확실히 알고 싶다면 이전의 풀이를 사용하면 되고,

성능을 생각한다면 현재의 풀이를 사용하면 된다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;
vector<pair<int, int>> parent(100001);

int right_node = -1;

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

	int left = parent[node].first;
	int right = parent[node].second;

	inorder(left, 0);

	if (flag == 1)
	{
		right_node++;
		inorder(right, 1);
	}
	else
	{
		inorder(right, 0);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int p, l, r;
		cin >> p >> l >> r;

		parent[p].first = l;
		parent[p].second = r;
	}

	inorder(1, 1);
	cout << ((N - 1) * 2) - right_node;
}