21W29-구현 - 04 분할정복

[moodmine]

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV3Fu8sqANIBBAQ3

[moodmine]

SWEA 1248. 공통조상

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_NODE_NUM 10000
#define MAX_CHILD_NUM 2

int nodeNum;
int edgeNum;
int root;
int route_a[100];
int route_b[100];
int size_root = 0;

typedef struct
{
    int parent;
    int child[MAX_CHILD_NUM];
} TreeNode;

TreeNode tree[MAX_NODE_NUM];

void initTree(void)
{
    int i;
    int j;
    for (i = 0; i <= nodeNum; i++)
    {
        tree[i].parent = -1;
        for (j = 0; j < MAX_CHILD_NUM; j++)
        {
            tree[i].child[j] = -1;
        }
    }
}

void addChild(int parent, int child)
{
    int i;
    for (i = 0; i < MAX_CHILD_NUM; i++)
    {
        if (tree[parent].child[i] == -1)
        {
            break;
        }
    }
    tree[parent].child[i] = child;
    tree[child].parent = parent;
}

int getRoot(void)
{
    int i;
    int j;
    for (i = 1; i <= nodeNum; i++)
    {
        if (tree[i].parent == -1)
        {
            return i;
        }
    }
    return -1;
}

void preOrder(int root)
{
    int i;
    int child;
    size_root++;

    for (i = 0; i < MAX_CHILD_NUM; i++)
    {
        child = tree[root].child[i];
        if (child != -1)
        {
            preOrder(child);
        }
    }
}

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);

    for (test_case = 1; test_case <= T; ++test_case)
    {
        int i = 0;
        int j = 0;
        size_root = 0;
        for (i = 0; i < 100; i++)
        {
            route_a[i] = 0;
            route_b[i] = 0;
        }
        int a, b;
        scanf("%d %d %d %d", &nodeNum, &edgeNum, &a, &b);

        initTree();

        int parent, child;

        for (int i = 0; i < edgeNum; i++)
        {
            scanf("%d %d", &parent, &child);
            addChild(parent, child);
        }
        i = 0;
        j = 0;

        while (a != 1)
        {
            for (i = 1; i <= nodeNum; i++)
            {
                if (tree[i].child[0] == a || tree[i].child[1] == a)
                {
                    route_a[j] = a;
                    a = i;
                    j++;
                }
            }
        }
        route_a[j] = 1;
        i = 0;
        j = 0;

        while (b != 1)
        {
            for (i = 1; i <= nodeNum; i++)
            {
                if (tree[i].child[0] == b || tree[i].child[1] == b)
                {
                    route_b[j] = b;
                    b = i;
                    j++;
                }
            }
        }
        route_b[j] = 1;

        i = 0;
        int result_1 = 0;
        int signal = 0;
        while (route_a[i] != 0)
        {
            j = 0;
            while (route_b[j] != 0)
            {
                if (route_a[i] == route_b[j])
                {
                    result_1 = route_b[j];
                    signal = 1;
                    break;
                }
                j++;
            }
            if (signal == 1)
            {
                signal = 0;
                break;
            }
            i++;
        }

        int result_2;
        int temp = 0;
        preOrder(result_1);

        printf("#%d %d %d\n", test_case, result_1, size_root);
    }
    return 0;
}