SWEA - 1248 공통 조상

문제

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

SW Expert Academy

트리를 입력받고 주어진 노드 2개의 공통 조상을 찾고, 해당 조상의 서브 트리 크기를 구하는 문제였다. 

 

문제 풀이

처음에 서브 트리 크기를 구하는 것을 서브 트리의 총 개수를 구한다고 생각했는데(풀진않고 생각만), 문제에 서브 트리 크기라고 아주 자세히 적혀 있었다. 

 

먼저 공통 조상을 찾는 과정에서는 주어진 노드의 레벨을 확인해 같은 레벨로 만들어주고, 한 단계씩 레벨을 올려 같은 조상이 나오면 그 노드 번호를 반환해 찾았다. 그리고는 해당 노드에서부터 dfs를 돌려 돌아간 횟수를 세어주며 간단하게 서브 트리 크기를 계산했다. 생각보다 간단하게 풀린 것 같다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>

using namespace std;

int V,E,s1,s2;
int parent[10001];
vector<int> G[10001];
int answer;

int findLevel(int a, int level){ //레벨 확인
    if(parent[a] == 0) return level;
    else return findLevel(parent[a], level+1);
}

int findSameParent(int a, int b){ //공통 조상 찾기
    //1. 각각의 레벨 확인    
    int levelA = findLevel(a, 1);
    int levelB = findLevel(b, 1);

    //2. 둘의 레벨 같게 맞춰주기 (레벨이 같은거보다 높은 곳이 조상)
    //항상 a가 b보다 level이 작게
    if(levelA > levelB){ //a,b 바꾸기
        int t = a;
        a = b;
        b = t;        
        t = levelA;
        levelA = levelB;
        levelB = t;
    }
    int parentA = a;
    int parentB = b;
    while(levelA != levelB){
        parentB = parent[b];
        b = parentB;
        levelB--;
    }
    
    //같이 레벨 올리면서 공동 조상 찾기
    while(parentA != parentB){
        parentA = parent[a];
        parentB = parent[b];
        a = parentA;
        b = parentB;
        //printf("parentA: %d parentB: %d\n",parentA, parentB);
    }    
    
    return parentA;
}

void dfs(int a){
    answer++;
    for(int i=0;i<G[a].size();i++){
        dfs(G[a][i]);
    }
}

void calServeTree(int r){
    dfs(r);    
}

void printParent(){
    for(int i=1;i<=V;i++){
        printf("%d의 부모: %d\n", i, parent[i]);
    }
    printf("\n");
}

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;
        answer = 0;
        cin >> V >> E >> s1 >> s2;
        fill(&parent[0], &parent[10000], 0);
        fill(&G[0], &G[10000], vector<int>());
		for(int i=0;i<E;i++){
            cin >> a >> b; //부모 자식
            G[a].push_back(b);
            parent[b] = a;
        }
        int sameParent = findSameParent(s1,s2);
        calServeTree(sameParent);
        
        printf("#%d %d %d\n",test_case, sameParent, answer);
	}
	return 0;
}