백준 1991(트리 순회)

jh Seo·2023년 1월 6일
0

백준

목록 보기
118/179

개요

백준1991번: 트리 순회

  • 입력
    첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

  • 출력
    첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

접근 방식

처음 접근한 방식

  1. 트리류 유형의 문제로 처음으로 접한 문제였다.
    배열에 값을 저장하며 부모 인덱스는 자식인덱스의 /2,
    자식인덱스는 부모인덱스의 *2, *2+1 이렇게 나타내는 방식으로
    [priority_queue 구현] 할 때 사용한 것 처럼 구현하였다.

  2. 처음에 벡터를 resize함수를 통해 (N+1)(N+2)/2의 크기로 할당해주고
    값들을 '.'으로 초기화했다.
    크기를 저렇게 정한 건 노드갯수가 7일때
    노드가 한쪽으로 쏠려있을 때 트리의 높이는 7까지 가능하고,
    자식 노드를 체크할때 해당 인덱스의 *2를 하여 다음 줄까지 체크하므로
    높이 1부터 높이 N+1까지 미리 생성해주기 위함이였다.

  3. 그 후, char값이 들어올 때 SetParentChildren함수를 통해
    tree배열에 저장해주었다.

    //부모랑 자식값을 서로 p, l ,r값으로 설정해주는 함수
    	void SetParentChildren(char p, char l, char r) {
    		//맨처음 세팅이면 루트값과 루트의 자식값 대입해줌.
    		if (treeArr[1] == '.') {
    			treeArr[1] = p;
    			treeArr[2] = l;
    			treeArr[3] = r;
    		}
    		//처음이아니라면 p값을 iterator로 찾아서 해당값의 자식에 넣어줌 
    		else {
    			for (int i = 1; i < treeArr.size();i++) {
    				if (treeArr[i] == p) {
    					treeArr[i * 2] = l;
    					treeArr[i * 2 + 1] = r;
    					break;
    				}
    			}
    		}
    	}

    인덱스 1이 루트여야한다.
    0이면 *2, *2+1를 해봐도 자식 인덱스가 안나옴.

배열크기를 최적화하는 방식

  1. 하지만 위의 방식으로 하면 입력되는 트리가
    heap처럼 완전 이진트리도 아닌데
    배열크기를 불필요하게 크게 잡아야하는 문제가 있어서
    다른 방식을 좀 검색해봤다.

  2. 노드값을 알파벳으로 주므로 입력값에 알파벳의 첫 글자인
    'A'값을 뺀다면 몇 번째 알파벳인지 알 수 있다.

  3. 따라서 배열의 사이즈를 알파벳의 갯수인 26개로 맞춰놓으면
    크기를 (N+1)*(N*2)/2만큼 할당을 안해줘도된다.

  4. i번째 알파벳의 부모 노드를 저장하는 배열 parent[26]과,
    i번째 알파벳의 자식 노드들을 저장하는 배열 leftChildren[26],
    rightChildren[26]을 설정해줬다.

  5. 그 후 부모노드와 자식 노드를 배열에 저장해 서로 연결해주는 함수
    SetPAndC를 적고 입력값마다 연결해주었다.

    //p번째 알파벳의 자식 노드로 lc,rc번째 알파벳 설정하고, 
    //lc,rc번째 알파벳의 부모노드로 p번째 알파벳으로 설정하는 함수
    void SetPAndC(int p, int lc, int rc) {
    	//p번째 알파벳의 왼쪽 자식 노드는 lc번째 알파벳, 
    	leftChildren[p] = lc;
    	//오른쪽 자식노드는 rc 번째 알파벳 값이 들어간다
    	rightChildren[p] = rc;
    	//lc,rc가 -1이면 저장할 의미도 없을 뿐더러 인덱스가 -1이 되면 안되기때문에 예외로 조사한다.
    	//lc번째 알파벳의 부모노드는 p번째 알파벳으로 설정
    	if(lc!=-1)parent[lc] = p;
    	//rc번째 알파벳의 부모노드는 p번째 알파벳으로 설정
    	if(rc!=-1)parent[rc] = p;
    }

1번째 방식 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class Tree {
public:
	int Node;
	vector<char> treeArr;

	Tree():Node(0) {}
	Tree(int N) :Node(N) {
		treeArr.resize((N+1)*(N+2)/2,'.');
	}
	//부모랑 자식값을 서로 p, l ,r값으로 설정해주는 함수
	void SetParentChildren(char p, char l, char r) {
		//맨처음 세팅이면 루트값과 루트의 자식값 대입해줌.
		if (treeArr[1] == '.') {
			treeArr[1] = p;
			treeArr[2] = l;
			treeArr[3] = r;
		}
		//처음이아니라면 p값을 iterator로 찾아서 해당값의 자식에 넣어줌 
		else {
			for (int i = 1; i <Node*(Node+1)/2;i++) {
				if (treeArr[i] == p) {
					treeArr[i * 2] = l;
					treeArr[i * 2 + 1] = r;
					break;
				}
			}
		}
	}
	// 왼쪽 자식 방문, 자기자신 방문, 오른쪽 자식 방문하는 중위 순위
	void InOrder(int root) {
    	//범위 안넘어가는지 체크 및 .인지 체크
		if (root*2<treeArr.size()&& treeArr[root * 2] != '.') InOrder(root * 2);
		cout << treeArr[root];
		if (root * 2+1 < treeArr.size() && treeArr[root * 2 + 1] != '.') InOrder(root * 2 + 1);
	}
	//자기 자신부터 방문하는 전위순회
	void PreOrder(int root) {
		cout << treeArr[root];
        //범위 안넘어가는지 체크 및 .인지 체크
		if (root * 2 < treeArr.size() && treeArr[root * 2] != '.') PreOrder(root * 2);
		if (root * 2+1 < treeArr.size() && treeArr[root * 2 + 1] != '.') PreOrder(root * 2 + 1);

	}
	//무조건 자식부터 방문하는 후위 순회
	void PostOrder(int root) {
   	 	//범위 안넘어가는지 체크 및 .인지 체크
		if (root * 2 < treeArr.size() && treeArr[root * 2] != '.') PostOrder(root * 2);
		if (root * 2+1 < treeArr.size() && treeArr[root * 2 + 1] != '.') PostOrder(root * 2 + 1);
		cout << treeArr[root];
	}
};
Tree* tree;

void Input() {
	int Nodes = 0;
	char parentNode = 0, leftNode = 0, rightNode = 0;
	cin >> Nodes;
	tree=new Tree(Nodes);
	for (int i = 0; i < Nodes; i++) {
		cin >> parentNode >> leftNode >> rightNode;
		tree->SetParentChildren(parentNode, leftNode, rightNode);
	}
}

void Solution() {
	tree->PreOrder(1);
	cout << '\n';
	tree->InOrder(1);
	cout << '\n';
	tree-> PostOrder(1);
}

int main() {
	Input();
	Solution();
}

2번째 방식 코드(배열 크기 최적화)

#include<iostream>

using namespace std;

//i번째 인덱스의 부모 노드값
int parent[26];
//i번째 인덱스의 왼쪽 자식 노드값
int leftChildren[26];
//i번째 이덱스의 오른쪽 자식 노드값
int rightChildren[26];

//p번째 알파벳의 자식 노드로 lc,rc번째 알파벳 설정하고, 
//lc,rc번째 알파벳의 부모노드로 p번째 알파벳으로 설정하는 함수
void SetPAndC(int p, int lc, int rc) {
	//p번째 알파벳의 왼쪽 자식 노드는 lc번째 알파벳, 
	leftChildren[p] = lc;
	//오른쪽 자식노드는 rc 번째 알파벳 값이 들어간다
	rightChildren[p] = rc;
	//lc,rc가 -1이면 저장할 의미도 없을 뿐더러 인덱스가 -1이 되면 안되기때문에 예외로 조사한다.
	//lc번째 알파벳의 부모노드는 p번째 알파벳으로 설정
	if(lc!=-1)parent[lc] = p;
	//rc번째 알파벳의 부모노드는 p번째 알파벳으로 설정
	if(rc!=-1)parent[rc] = p;
}
void Input() {
	//미리 부모, 자식 배열들 -1로 초기화
	fill(parent,parent+26,-1);
	fill(leftChildren,leftChildren+26,-1);
	fill(rightChildren,rightChildren+26,-1);
	int N=0;
	char parent=' ', leftChild = ' ', rightChild = ' ';
	cin >> N;
	//N만큼 반복해서 받음
	for (int i = 0; i < N; i++) {
		cin >> parent >> leftChild >> rightChild;
		//만약 왼쪽 자식만 .이라면
		if (leftChild == '.'&&rightChild!='.') {
			//해당 char값에 'A'를 빼주면 해당 알파벳의 인덱스가 나옴.
			//왼쪽자식에 -1값을 저장
			SetPAndC(parent-'A', -1, rightChild - 'A');
			continue;
		}
		//오른쪽만 .이라면
		else if (leftChild != '.' && rightChild == '.') {
			//오른쪽값에 -1을 저장
			SetPAndC(parent-'A', leftChild-'A', -1);
			continue;
		}
		//둘다 .이라면
		else if (leftChild == '.' && rightChild == '.') {
			//왼쪽 오른쪽 자식 다 -1 대입
			SetPAndC(parent-'A', -1, -1);
			continue;
		}
		//.이 없다면 해당 알파벳에 해당하는 인덱스값으로 설정 
		SetPAndC(parent-'A', leftChild-'A', rightChild-'A');
	}
}
//전위 순회
void PreOrder(int root) {

	cout << (char)(root+'A');

	if (leftChildren[root] != -1) PreOrder(leftChildren[root]);

	if (rightChildren[root] != -1) PreOrder(rightChildren[root]);
}
//중위 순회
void InOrder(int root) {
	if (leftChildren[root] != -1) InOrder(leftChildren[root]);
	cout << (char)(root+'A');
	if (rightChildren[root] != -1) InOrder(rightChildren[root]);
}
//후위 순회
void PostOrder(int root) {
	if (leftChildren[root] != -1) PostOrder(leftChildren[root]);
	if (rightChildren[root] != -1) PostOrder(rightChildren[root]);
	cout << (char)(root+'A');
}


void Solution() {
	PreOrder(0);
	cout << '\n';
	InOrder(0);
	cout << '\n';
	PostOrder(0);
}

int main() {
	Input();
	Solution();
}

문풀후생

알파벳으로 입력값이 준다면 'A'을 이용해서 배열을 처리하는 방식은
많이 다뤘는데 좀더 바로바로 생각나게끔 활용을 더 많이 해야겠다

profile
코딩 창고!

0개의 댓글