[2019 카카오] 길 찾기 게임

programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> info;
vector<int> order;

class Node {
public:
	int no;
	Node *left;
	Node *right;

	Node(int no) : no(no) {
		left = nullptr;
		right = nullptr;
	};

	void insert(Node *node) {
		// 왼쪽으로 가는 경우
		if (info[node->no][0] < info[no][0]) {
			if (left == nullptr) left = node;
			else left->insert(node);
		}
		// 오른쪽으로 가는 경우
		else {
			if (right == nullptr) right = node;
			else right->insert(node);
		}
	}

	void preorder(vector<int> &order) {
		order.push_back(no + 1);
		if (left != nullptr) left->preorder(order);
		if (right != nullptr) right->preorder(order);
	}

	void postorder(vector<int> &order) {
		if (left != nullptr) left->postorder(order);
		if (right != nullptr) right->postorder(order);
		order.push_back(no + 1);
	}
};

bool cmp(int a, int b) {
	return info[a][1] > info[b][1];
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
	info.assign(nodeinfo.begin(), nodeinfo.end());
	order.resize(nodeinfo.size());
	for (int i = 0; i < order.size(); i++) order[i] = i;
	sort(order.begin(), order.end(), cmp);

	Node root(order[0]);
	for (int i = 1; i < order.size(); i++) {
		Node *node = new Node(order[i]);
		root.insert(node);
	}

	vector<vector<int>> answer(2);
	root.preorder(answer[0]);
	root.postorder(answer[1]);

	return answer;
}

 

기본적인 트리 구현만 할 줄 안다면 쉽게 풀 수 있는 문제

order 배열은 nodeinfo 배열을 y값으로 내림차순한 인덱스의 순서를 저장한 배열이다.

order 순서대로 트리를 만들면 심플하게 로직을 짤 수 있다

 

(+)

visual studio에서는 포인터를 null로 초기화해주지 않아도 에러가 안떴는데

프로그래머스에서는  안해주면 segmentation fault가 뜬다.

이거때문에 좀 삽질함..