[SWEA] 1248 공통조상 (c++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD

SW Expert Academy

풀이 과정

• 문제에서 나온 것처럼 이진트리를 구현하는게 먼저라고 생각했습니다.
• 공통 조상을 찾기위해서 하나를 root노드까지 쭉 검사해서 그 경로를 비교하는 것이 아니라, 각각 번갈아 가면서 parent를 조사하고 조사된 노드들을 표시해놓습니다. 다른 노드가 검사했을 때, 이미 조사되었다고 나온다면 그것이 가장 가까운 공통 조상이 됩니다. 이렇게 하면 root까지 조사할 필요가 없습니다.
• 이진 트리이고 중간에 값이 업데이트가 되는 것이 아니라 그냥 자식의 수를 구하는 것이기에 segment tree는 적절하지 않다고 생각을 했고, 전체 정점의 개수가 10000이기 때문에 dfs와 같이 재귀적으로 구현해도 된다고 생각했습니다. 

풀이 코드

#include<iostream>

#define MAX 10001
using namespace std;

struct Node{
    int parent;
    int child[2];
};

Node tree[MAX];
bool visited[MAX];
int subtree_size;

int findCommonAncestor(int vertex1, int vertex2){
    int commonParent = 1;
    int vertex1_parent;
    int vertex2_parent;
    while(true){
        if(vertex1 != 1){
            vertex1_parent = tree[vertex1].parent;
            if(visited[vertex1_parent]){
                commonParent = vertex1_parent;
                break;
            }
            visited[vertex1_parent] = true;
            vertex1 = vertex1_parent;
        }

        if(vertex2 != 1){
            vertex2_parent = tree[vertex2].parent;
            if(visited[vertex2_parent]){
                commonParent = vertex2_parent;
                break;
            }
            visited[vertex2_parent] = true;
            vertex2 = vertex2_parent;
        }
    }
    return commonParent;
}

void calSize(int root){
    if(tree[root].child[0] != 0){
        subtree_size++;
        calSize(tree[root].child[0]);
    }

    if(tree[root].child[1] != 0){
        subtree_size++;
        calSize(tree[root].child[1]);
    }
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	int test_case;
	int T;
    int vertex_num;
    int edge_num;
    int find_vertex1;
    int find_vertex2;
    int parent_num;
    int child_num;
    int closest_common_ancestor;
	cin>>T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
        subtree_size = 1; // 자기 자신도 포함하니까
        for(int i = 1; i <= MAX; i++){
            tree[i].parent = 0;
            tree[i].child[0] = 0;
            tree[i].child[1] = 0;
            visited[i] = false;
        }

        cin >> vertex_num >> edge_num >> find_vertex1 >> find_vertex2;

        for(int i = 0; i < edge_num; i++){
            cin >> parent_num >> child_num;
            
            tree[child_num].parent = parent_num;
            if(tree[parent_num].child[0] == 0){
                tree[parent_num].child[0] = child_num;
            }else{
                tree[parent_num].child[1] = child_num;      
            }
        }

        closest_common_ancestor = findCommonAncestor(find_vertex1, find_vertex2);
    
        calSize(closest_common_ancestor);
 
        cout << "#" << test_case << " " << closest_common_ancestor << " " << subtree_size << '\n';
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}