[C++] 카카오 코딩테스트 < 길 찾기 게임 > 문제풀이

풀이

---

바로 본론으로 갑시다.

여기로 가시면 문제를 풀어보실 수 있습니다.

 

 

문제를 읽어보니 전무로 승진한 라이언이 사원들을 위해서

무언가 엄청 분석하고 있습니다.

하지만, 문제에서 요구하는 것은 간단합니다.

기본적인 트리를 구현하고

전위순회와 후위 순회를 수행해라.

 

 

트리 구현이 필수적인 경우엔 반드시

필요한 요소만을 구현할 필요가 있습니다.

 

 

기본적으로 자료구조에서 배운 트리는 Value 값만을 갖고

왼쪽 자식, 오른쪽 자식을 구별합니다.

 

 

저는 이 문제를 해결하기 위해 TreeNode 의 멤버 변수로

x, y, value

를 사용했습니다.

 

y 는 상대적인 depth 를 의미합니다.

x 는 크기를 비교하는 key 값이 됩니다.

value는 실질적으로 답이 되는 값입니다.

 

 

Tree 의 구현은 자료구조 개념과 같으니 생략하겠습니다.

 

 

Solution 함수를 보시면

우선 answer 컨테이너의 사이즈를 2로 맞추어줬습니다.

두 번의 순회를 하면서 값을 저장하기 위해서입니다.

 

 

vector 컨테이너를 TreeNode* 의 Type 으로 선언해주었습니다.

여러 개의 노드를 한 번에 생성하기 위함도 있지만

Y(depth) 값이 큰 값부터 트리에 입력해주어야 하기 때문에

정렬하는 과정이 따로 필요하기 때문입니다.

 

 

algorithm 헤더에 있는 sort 함수를 사용할 건데

저희는 y 값을 기준으로 정렬을 해야 하니 비교 함수 cmp 를 따로 생성해줍시다.

bool cmp(TreeNode* a , TreeNode* b) {
	return a->y > b->y; //내림차순
    //return a->y < b->y; //오름차순
}

 

마지막으로 add() 함수를 통해서 노드를 모두 연결해준 뒤

전위 순회와 후위 순회를 통해 답을 입력해줍니다.

모르는 부분은 댓글에 남겨주세요.

 

코드

---

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

using namespace std;

class TreeNode {
public :
	int x;
	int y;
	int value;

	TreeNode* left;
	TreeNode* right;

	TreeNode(int x, int y, int value) {
		this->x = x;
		this->y = y;
		this->value = value;
		this->left = NULL;
		this->right = NULL;
	}
	~TreeNode() {
		delete this;
	}

};
// 노드 추가
void add(TreeNode* node, TreeNode* newNode) {
	if (node->x < newNode->x) {
		if (node->right == NULL) {
			node->right = newNode;
		}
		else {
			add(node->right, newNode);
		}
	}
	else if (node->x > newNode->x) {
		if (node->left == NULL) {
			node->left = newNode;
		}
		else {
			add(node->left, newNode);
		}
	}
	// 같은 경우는 애초에 트리로 만들지 않는다.
	return;

}

//전위 순회
void preorder(TreeNode* node, vector<int>& lst) {
	if (node == NULL) return;
	lst.push_back(node->value);
	preorder(node->left, lst);
	preorder(node->right, lst);
}

//후위 순회
void postorder(TreeNode* node, vector<int>& lst) {
	if (node == NULL) return;
	postorder(node->left, lst);
	postorder(node->right, lst);
	lst.push_back(node->value);
}

//sort 비교함수
bool cmp(TreeNode* a, TreeNode* b) {
	return a->y > b->y;
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
	vector<vector<int>> answer(2);
	vector<TreeNode*> l(nodeinfo.size());

	for (int i = 0; i < nodeinfo.size(); i++) {
		l[i] = new TreeNode(nodeinfo[i][0], nodeinfo[i][1],i+1);
		
	}
	sort(l.begin(), l.end(), cmp);

	for (int i = 1; i < l.size(); i++) {
		add(l[0], l[i]);
	}

	preorder(l[0], answer[0]);
	postorder(l[0], answer[1]);
	return answer;
}