백준 12767 Ceiling Function

https://www.acmicpc.net/problem/12767

트리의 모양이 총 몇개인지 묻는 문제입니다. 정말 많은 풀이 방법이 있겠지만 저는 linked-list를 오랜만에 구현했습니다.

트리 탐색 기억나시나요? 전위 탐색과 중위 탐색 결과를 안다면 우리는 트리의 모양을 확정지을 수 있습니다.

따라서 저는 입력으로 들어온 트리에 전위탐색 결과가 1,2, …,n 이 되도록 저장한 후, 후위탐색을 하여 이를 map에 저장하도록 하겠습니다.

#include<bits/stdc++.h>
using namespace std;
map<string,int> vst;
struct Point{
	int num;
	int ord;
	Point *left;
	Point *right;
};
Point *root;
int p;
void connect_link(Point *crt, int data){
	if(data<crt->num){
		if(crt->left==NULL){
			Point *tmp=(Point *)malloc(sizeof(Point));
			tmp->num=data; tmp->left=NULL; tmp->right=NULL;
			crt->left=tmp;			
		}
		else connect_link(crt->left,data);
	}
	else{
		if(crt->right==NULL){
			Point *tmp=(Point *)malloc(sizeof(Point));
			tmp->num=data; tmp->left=NULL; tmp->right=NULL;
			crt->right=tmp;			
		}
		else connect_link(crt->right,data);		
	}
}
void pre_order(Point *crt){
	if(crt==NULL) return;
	crt->ord=++p;
	pre_order(crt->left);
	pre_order(crt->right);
}
string in_order(Point *crt){
	if(crt==NULL) return "";
	return in_order(crt->left)+char(32+crt->ord)+in_order(crt->right);
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n,k; cin>>n>>k;
	int ans=0;
    root=(Point *)malloc(sizeof(Point));
	for(int i=0;i<n;i++){
		int x; cin>>x;
		p=0;
		root->num=x; root->left=NULL; root->right=NULL;
		for(int j=1;j<k;j++){
			int x; cin>>x;			
			connect_link(root,x);
		}
		pre_order(root);
		string tmp=in_order(root);
		if(vst[tmp]==0){
			ans++;
			vst[tmp]=1;
		}
	}
	cout<<ans;
	return 0;
}