개요
-
입력
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다. -
출력
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
접근 방식
처음 접근한 방식
-
트리류 유형의 문제로 처음으로 접한 문제였다.
배열에 값을 저장하며 부모 인덱스는 자식인덱스의 /2,
자식인덱스는 부모인덱스의 *2, *2+1 이렇게 나타내는 방식으로
[priority_queue 구현] 할 때 사용한 것 처럼 구현하였다. -
처음에 벡터를 resize함수를 통해 (N+1)(N+2)/2의 크기로 할당해주고
값들을 '.'으로 초기화했다.
크기를 저렇게 정한 건 노드갯수가 7일때
노드가 한쪽으로 쏠려있을 때 트리의 높이는 7까지 가능하고,
자식 노드를 체크할때 해당 인덱스의 *2를 하여 다음 줄까지 체크하므로
높이 1부터 높이 N+1까지 미리 생성해주기 위함이였다. -
그 후, 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를 해봐도 자식 인덱스가 안나옴.
배열크기를 최적화하는 방식
-
하지만 위의 방식으로 하면 입력되는 트리가
heap처럼 완전 이진트리도 아닌데
배열크기를 불필요하게 크게 잡아야하는 문제가 있어서
다른 방식을 좀 검색해봤다. -
노드값을 알파벳으로 주므로 입력값에 알파벳의 첫 글자인
'A'값을 뺀다면 몇 번째 알파벳인지 알 수 있다. -
따라서 배열의 사이즈를 알파벳의 갯수인 26개로 맞춰놓으면
크기를 (N+1)*(N*2)/2만큼 할당을 안해줘도된다. -
i번째 알파벳의 부모 노드를 저장하는 배열 parent[26]과,
i번째 알파벳의 자식 노드들을 저장하는 배열 leftChildren[26],
rightChildren[26]을 설정해줬다. -
그 후 부모노드와 자식 노드를 배열에 저장해 서로 연결해주는 함수
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'을 이용해서 배열을 처리하는 방식은
많이 다뤘는데 좀더 바로바로 생각나게끔 활용을 더 많이 해야겠다
코딩 창고!