[프로그래머스/알고리즘]길찾기 게임

길찾기 게임

입출력 예

nodeinfo : [[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]]

result : [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

해결 방법

이진 트리를 만드는 방법은 보통 2가지로 알고 있습니다. 첫번째는 배열을 통해서 2를 곱했을때와 왼쪽 트리, 2를 곱하고 1를 더했을 때 오른쪽 트리를 이용해서 문제를 풀어 나갈 수 있고 클래스나 구조체를 이용해서 linked list 형식으로 왼쪽 link와 오른쪽 link로 이동하는 방법을 통해서 구현할 수 있습니다.

저는 후자를 선택했는데요 

인덱스 값을 저장해야하기 때문에 nodeinfo에 각각의 인덱스 번호 값을 추가했고, 입력값들이 무작위라서 위에서부터 노드를 달아야 하기 때문에 nodeinfo를 정렬했습니다.  y좌표는 높은 순으로 x는 낮은 순으로 정렬했습니다.

정렬을 하고 가장 첫번째 값은 루트가 되기 때문에 루트를 만들었습니다.

 

그 이후 그다음 데이터에서 x축을 비교해서 x보다 작으면 왼쪽 노드, x보다 크면 오른쪽 노드로 이동했습니다. 왼쪽 노드와 오른쪽 노드가 NULL일 경우 구조체를 만들어 주고 값을 넣어 줬습니다.

그다음 전위 순회와 후위 순회를 구해야 합니다. 전위는 자신, 왼쪽노드, 오른쪽 노드 순으로 탐색하고 후위는 왼쪽 노드, 오른쪽 노드, 자신 순으로 탐색합니다. 이것을 재귀함수로 구현해서 구하면 정답이 나옵니다.

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Tree {
	int x;
	int y;
	int index;
	Tree * left;
	Tree * right;
};

vector<int> postcircuit(const Tree *tree, vector<int> &post) {
	if (tree->left != NULL)	postcircuit(tree->left, post);
	if (tree->right != NULL) postcircuit(tree->right, post);
	post.push_back(tree->index);

	return post;
}
vector<int> precircuit(const Tree *tree, vector<int> &pre) {
	pre.push_back(tree->index);
	if (tree->left != NULL)	precircuit(tree->left, pre);
	if (tree->right != NULL) precircuit(tree->right, pre);
	return pre;
}

bool pred(vector<int> a, vector<int> b) {
	if (a[1] == b[1])
		return a[0] < b[0];
	else
		return a[1] > b[1];
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
	vector<vector<int>> answer;
	//인덱스 번호 추가
	for (int i = 0; i < nodeinfo.size(); i++) 
		nodeinfo[i].push_back(i + 1);
	
	sort(nodeinfo.begin(), nodeinfo.end(), pred);

	//root tree
	Tree tree = { nodeinfo[0][0] ,nodeinfo[0][1],nodeinfo[0][2],NULL,NULL };
	Tree * iterator;
	for (int i = 1; i < nodeinfo.size(); i++) {
		iterator = &tree;
		while (1) {
			if (iterator->x > nodeinfo[i][0]) {		//왼쪽 노드
				if (iterator->left == NULL) {
					iterator->left = new Tree{ nodeinfo[i][0],nodeinfo[i][1] ,nodeinfo[i][2],NULL,NULL };
					break;
				}
				else
					iterator = iterator->left;
				}
			else {
				if (iterator->right == NULL) {
					iterator->right = new Tree{ nodeinfo[i][0],nodeinfo[i][1] ,nodeinfo[i][2],NULL,NULL };
					break;
				}
				else
					iterator = iterator->right;
    			}
			}
	}
	vector<int> pre;
	vector<int> post;
	answer.push_back(precircuit(&tree,pre));
	answer.push_back(postcircuit(&tree,post));

	return answer;
}