프로그래머스 - 길 찾기 게임 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 이번 문제는 각 노드들의 좌표가 주어졌을 때, 이 노드들로 구성된 트리의 전위 순회(preorder)와 후위 순회(postorder)의 결과를 출력하는 문제이다. 전위 순회나 후위 순회는 특별하게 어렵지 않다. 전위 순회의 경우에는 어떤 노드에서 노드 번호를 출력한 후, 왼쪽 노드를 방문하고 오른쪽 노드를 방문하면 된다. 그리고 후위 순회의 경우에는 어떤 노드에서 왼쪽 노드를 방문하고 오른쪽 노드를 방문한 후  노드 번호를 출력하면 된다. 그렇기에 이번 문제에서 신경써야 할 부분은 바로 트리 만들기이다.

 트리를 만들기 위해서는 노드들의 좌표를 이용해야 한다. 두 노드를 비교했을 때, y값이 더 큰 노드가 루트 노드에 가까울 것이다. 이를 이용하여 루트 노드를 알아낸 후, 루트 노드 외의 노드들을 차례대로 트리에 포함시킨다. 이렇게 만들어진 트리를 이용하면 답을 찾아낼 수 있다.

1. nodeinfo의 정보들을 더 자세히 하여 저장한다.
2. 노드들을 y, x 위치에 따라 정렬한다. 이 때, 정렬 기준은 다음과 같다. y 값이 더 클수록, 그리고 x값이 더 작을수록 앞으로 온다. 그리고 정렬된 노드들 중, 가장 앞에 있는 노드가 루트 노드이다.(가장 위에 있으므로)
3. 트리를 생성한다.
4. 각각의 순회 결과를 저장한다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 노드 타입형
typedef struct NODE
{
	int x;
	int y;
	int index;
	NODE* left;
	NODE* right;
} Node;

Node* rootNode;
vector<Node> nodes;
vector<int> preorder;
vector<int> postorder;

bool Compare(Node a, Node b)
{
	if (a.y > b.y) 
		return true;
	else if(a.y < b.y) 
		return false;
	else
	{
		if (a.x < b.x)
			return true;
		else
			return false;
	}
}

void MakeTree(Node* parentNode, Node* childNode)
{
	if (childNode->x < parentNode->x)
	{
		if (parentNode->left == NULL)
		{
			parentNode->left = childNode;
			return;
		}

		MakeTree(parentNode->left, childNode);
	}
	else if (parentNode->x < childNode->x)
	{
		if (parentNode->right == NULL)
		{
			parentNode->right = childNode;
			return;
		}

		MakeTree(parentNode->right, childNode);
	}
}

// 전위 순회를 하는 함수
void Preorder(Node* node)
{
	if (node == NULL)
		return;

	preorder.push_back(node->index);
	Preorder(node->left);
	Preorder(node->right);
}

// 후위 순회를 하는 함수
void Postorder(Node* node)
{
	if (node == NULL)
		return;

	Postorder(node->left);
	Postorder(node->right);
	postorder.push_back(node->index);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo)
{	
	// 1. nodeinfo의 정보들을 더 자세히 하여 저장한다.
	for (int i = 0; i < nodeinfo.size(); ++i)
	{
		int x = nodeinfo[i][0];
		int y = nodeinfo[i][1];

		Node node;
		node.x = x;
		node.y = y;
		node.index = i + 1;
		node.left = NULL;
		node.right = NULL;

		nodes.push_back(node);
	}

	// 2. node들을 y, x 위치에 따라 정렬한다. (기준 1: y좌표가 클수록 앞으로. 기준 2: x좌표가 작을수록 앞으로)
	sort(nodes.begin(), nodes.end(), Compare);

	// 이 때, 가장 앞에 오는 노드가 root node이다. (가장 꼭대기에 있는 노드)
	rootNode = &nodes[0];

	// 3. 트리를 생성한다.
	for (int i = 1; i < nodes.size(); ++i)
		MakeTree(rootNode, &nodes[i]);
	
	// 각각의 순회 결과를 저장한다.
	Preorder(rootNode);
	Postorder(rootNode);

	return { preorder, postorder };
}