프로그래머스 Level 3 길찾기게임

길찾기게임 (프로그래머스 Level 3)

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

문제 자체는 크게 3 개의 구현을 요구하는데

1. 좌표가 주어지고 그것을 각각의 노드로 보는 것
   
2. 그 노드들을 ‘연결’하기
   
3. 연결된 트리를 각각 ‘전위’, ‘후위’ 순회
   

먼저 각 단계에서의 y 좌표값은 같다 하였으므로
입력값으로 주어진 벡터를 y 기준으로 정렬해준다
(이 때, 원래 주어진 index를 기록하기 위하여
node라는 구조체를 하나 생성하여 전부 저장을 해두었다)

이후, treeNode 구조체를 생성하고
node와 left, right 를 각각 unique_ptr로 생성
(최근, 스마트 포인터를 배우고 난 후, 코테 등에서는 이걸 사용하는 것이
조금 더 깔끔하고 편리하다고 느끼고 있다)

insert할 때, node의 x 좌표를 이용하여
현재 자신보다 ‘작다’면 left, 아니면 right로 생성시킨다

이후, 순회할 때
전위는 ‘현재 노드’ -> ‘left’ -> ‘right’ 로
후위는 ‘left’ -> ‘right’ -> ‘현재 노드’ 로
재귀적으로 temp 벡터에 담아주는 방식으로 풀었다

구현 자체는 그렇게 어렵지는 않았으나
여러 개념을 합치고 응용해서 풀 수 있었다는 점이
인상에 남은 문제였다

Code

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

using namespace std;

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
	vector<vector<int>> answer;

	struct node
	{
		int index;
		int x;
		int y;
	};

	vector<node> vec;
	for (int i = 0; i < nodeinfo.size();i++)
	{
		vec.push_back(node{i + 1,nodeinfo[i][0],nodeinfo[i][1]});
	}

	sort(vec.begin(), vec.end(), [](const node& a, const node& b) {
		if (a.y == b.y)
			return a.x < b.x;

		return a.y > b.y;
		});

	// tree 만들어서 넣기

	struct treeNode
	{
		node value;
		unique_ptr<treeNode> left;
		unique_ptr<treeNode> right;

		void insert(node _value)
		{
			if (value.x > _value.x)
			{
				if (left == nullptr)
				{
					left = make_unique<treeNode>();
					left->value = _value;
				}
				else
				{
					left->insert(_value);
				}
			}
			else if (value.x < _value.x)
			{
				if (right == nullptr)
				{
					right = make_unique<treeNode>();
					right->value = _value;
				}
				else
				{
					right->insert(_value);
				}
			}
		}

		void preOrder(vector<int>& answer)
		{
			answer.push_back(value.index);
			if(left != nullptr)
				left->preOrder(answer);
			if (right!= nullptr)
				right->preOrder(answer);
		}

		void postOrder(vector<int>& answer)
		{
			if (left != nullptr)
				left->postOrder(answer);

			if (right != nullptr)
				right->postOrder(answer);

			answer.push_back(value.index);
		}
	};

	treeNode root = { vec[0],nullptr,nullptr };

	for (int i = 1; i < vec.size(); i++)
	{
		root.insert(vec[i]);
	}

	vector<int> temp;
	root.preOrder(temp);
	answer.push_back(temp);
	temp.clear();
	root.postOrder(temp);
	answer.push_back(temp);

	return answer;
}