SWEA - 공통조상 (C++)

문제

https://swexpertacademy.com/main/talk/codeBattle/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD&categoryId=AYIPD136YD8DFATO&categoryType=BATTLE&battleMainPageIndex=1 

SW Expert Academy

 

풀이

트리는 구조체로 구현하고, 공통 조상을 찾은 후, 서브트리의 크기는 BFS로 알아낸다.

공통조상을 알아내는 것은 그냥 단순하게 정점들을 방문하고 비교해보면서 찾아냈는데 더 좋은 방법이 있을 것 같다..

트리를 구현하는 것은 구조체의 배열을 이용해서 인덱스로 접근 가능하도록 했다.

 

코드

#include<iostream>
#include<queue>
using namespace std;

struct node
{
    int data;
    struct node *child[2];
    struct node *parent;
    int cnt;
}nodes[10001];

node* getNode(int data) {
	nodes[data].data = data;
	nodes[data].child[0] = nullptr;
    nodes[data].child[1]=nullptr;
    nodes[data].parent=nullptr;
    nodes[data].cnt=1;
	return &nodes[data];
}

void addNode(int n, int a)
{
    if(nodes[n].data!=n) node*newnode = getNode(n);
    if(nodes[a].data!=a) node*cnode = getNode(a);
    if(nodes[n].child[0]==0) nodes[n].child[0]=&nodes[a];
    else nodes[n].child[1]=&nodes[a];
    nodes[a].parent=&nodes[n];
    node *cur = &nodes[n];
}

int findpar(int a, int b)
{
    int res=0;
    int arr[10000];
    int idx=0;
    bool flag = false;
    node *cur = &nodes[a];
    while(cur->parent!=0)
    {
        cur=cur->parent;
        arr[idx]=cur->data;
        idx++;
    }
    node*tmp = &nodes[b];
    while(tmp->parent!=0)
    {
        if(flag) break;
        tmp=tmp->parent;
        for(int i=0; i<idx; i++)
        {
            if(tmp->data==arr[i])
            {
                res=arr[i];
                flag=true;
                break;
            }
        }
    }
    return res;
}

int countchild(int n)
{
    queue<int> q;
    q.push(n);
    int count =1;
    
    while(!q.empty())
    {
     	int cur=q.front();
        q.pop();
        
        for(int i=0; i<2; i++)
        {
         	if(nodes[cur].child[i]!=nullptr)
            {
                q.push(nodes[cur].child[i]->data);
                count++;
            }
        }
    }
    return count;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        for(int i=0; i<b; i++)
        {
            int n,m;
            cin>>n>>m;
            addNode(n,m);
        }
        int r = findpar(c,d);
        int res = countchild(r);
        //int r=1;
        
        printf("#%d %d %d\n",test_case,r,res);
        if(test_case<10)
        {
        	for(int i=0; i<=a; i++)
        	{
            	nodes[i].cnt=1;
            	nodes[i].data=0;
            	nodes[i].child[0]=0;
            	nodes[i].child[1]=0;
            	nodes[i].parent=0;
        	}
        }
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}