[c++/프로그래머스] 길 찾기 게임

문제 링크

길 찾기 게임

풀이

이진트리를 만들고 순회하는 문제

1. 먼저 Node 구조체를 만들어준다.
   1-1. 순회해서 인덱스를 출력해야 하므로 data, 위치값인 x, y, 왼쪽 자식 노드 포인터 left와 오른쪽 자식 노드 포인터 right
   1-2. 처음엔 생성자를 만들어줬는데 그럴 필요 없음 ..
2. Node 벡터를 만들어주고 초기화 해준 뒤, 정렬을 해주어야 함
   2-1. y 값으로 내림차순 정렬, x 값으로 오름차순 정렬해준다. 해당 커스텀 정렬 함수는 compare
3. 정렬 후 0번째 노드는 제일 위에 있는 노드이므로 root가 된다. 1번째 노드부터 부모에 연결해준다. 해당 함수는 setParent
   3-1. 부모 노드 포인터인 parent의 x값이 해당 노드 x값 보다 크다면 왼쪽에 있다는 것. 부모의 왼쪽 자식 노드가 NULL이라면 해당 노드가 그 부모의 왼쪽 자식 노드가 된다. 이미 자식이 있다면 해당 왼쪽 자식 노드를 다시 부모로 재귀호출해준다. 오른쪽도 마찬가지로 진행
4. 이진트리의 순회는 재귀호출로 쉽게 가능하다. 전위순회는 해당노드->왼쪽자식->오른쪽자식, 후위순회는 왼쪽자식->오른쪽자식->해당노드 순이 된다. 해당 노드일 때는 data 값을 넣고, 자식 노드일 때는 재귀호출 해주면 된다. 물론 NULL 체크도 해줘야 널 익셉션이 안뜸

코드

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

using namespace std;

struct Node
{
	int data;
	int x, y;
	Node* left;
	Node* right;

	Node(int _data, int _x, int _y) : data(_data), x(_x), y(_y)
	{
		left = NULL;
		right = NULL;
	}
};

bool compare(Node a, Node b)
{
	if (a.y == b.y) return a.x < b.x;
	else return a.y > b.y;
}

void setParent(Node* parent, Node* node)
{
	if (parent->x > node->x) // 왼쪽에 있음
	{
		if (parent->left == NULL)
		{
			parent->left = node;
			return;
		}
		setParent(parent->left, node);
	}
	else // 오른쪽에 있음
	{
		if (parent->right == NULL)
		{
			parent->right = node;
			return;
		}
		setParent(parent->right, node);
	}
}

void preorder(Node* root, vector<int> &pre)
{
    pre.push_back(root->data);
    if(root->left != NULL) preorder(root->left, pre);
    if(root->right != NULL) preorder(root->right, pre);
}

void postorder(Node* root, vector<int> &post)
{
    if(root->left != NULL) postorder(root->left, post);
    if(root->right != NULL) postorder(root->right, post);
    post.push_back(root->data);
}

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

	vector<Node> tree;
	for (int i = 0; i < nodeinfo.size(); i++)
	{
		tree.push_back({ i + 1, nodeinfo[i][0], nodeinfo[i][1] }); // x,y,인덱스
	}

	sort(tree.begin(), tree.end(), compare); // y 내림차순, x 오름차순 정렬

	Node* root = &tree[0]; // 루트 노드
	for (int i = 1; i < tree.size(); i++) // 트리 만들어주기
	{
		setParent(root, &tree[i]);
	}
    
    vector<int> answer1;
    preorder(root, answer1);
    
    vector<int> answer2;
    postorder(root, answer2);
    
    answer.push_back(answer1);
    answer.push_back(answer2);
    
	return answer;
}