[백준 3584]- 가장 가까운 조상(C++)[골드4]

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11을 모두 자손으로 갖는 노드는 4와 8이 있지만, 그중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

 

🔎문제 해석

자식은 하나의 부모를 갖기 때문에 인접행렬식으로 저장해서 부모, 자식 관계를 표현했습니다.
가장 가까운 조상은 우선 A 노드에 부모를 계속 탐색하면서, 부모를 저장하고, B 노드를 탐색할 때 A노드의 부모를 만난다면, 그때 부모가 가장 가까운 조상일 것입니다.
왜냐하면 가장 가까운 부모를 계속 호출해서 깊게 파고 들어가는 형식이기 때문입니다.

 

💡문제 풀이

1. 인접행렬로 부모-자식과의 관계를 표현합니다.
   1. 한명의 부모가 여러 명의 자식을 가지기 때문에, node [자식]-> 부모 형식으로 연결해 줍니다.
2. A노드의 부모를 저장하기 위해서 map을 사용했습니다.
   1. 굳이 map을 사용하지 않아도 될 거 같은데 find함수를 쓰기 위해서 사용했습니다.
3. 부모를 찾는 함수는 재귀함수를 사용했습니다.
   1. 부모를 계속해서 map에  insert 하고, 만약 더 이상 부모가 없다면 함수를 종료했습니다.
4. B노드(두 번째 노드)는 부모를 타고 올라가면서 map에 있는 원소와 일치한다면 그때 부모를 출력하고 함수를 종료했습니다.

 

이런 식으로 만 풀리면 정말 좋았을 문제였지만, 제출하니까 35%? 에서 틀려서 왜 그런지 찾아보니까

A, B노드가 서로의 공통부모가 될 수 있는 가능성을 생각안해줘서 그랬습니다.

그래서 map에 A,B 노드에 해당하는 숫자도 insert 했습니다.

 

 

💻전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int t,n,p,c,node1,node2;
map<int,int>m;
void search(vector<int>tree[],int first, int depth);
void second_search(vector<int>tree[],int first, int depth);
int main(){
    cin>>t;
    for(int test = 0; test<t; test++){
        cin>>n;
        vector<int>tree[n+1];
        for(int node= 0; node<n-1; node++){ //n-1개 까지 입력받음.
            cin>>p>>c; // 부모 -> 자식 순으로 입력받음.
            tree[c].push_back(p); 
        }
        cin>>node1>>node2; //node1과 node2의 공통조상을 찾아야함.
        m.insert(make_pair(node1,0));
        search(tree,node1,0);
        second_search(tree,node2,0);
        m.clear();
    }
}
void search(vector<int>tree[],int first, int depth)
{
    if(tree[first].size()==0) //만약 더이상 부모가 없다면 종료함.
        return;
    int parent = tree[first][0];
    m.insert(make_pair(parent,depth+1));
    if(m.find(node2)!=m.end()) //node2가 부모라면 가장 가까운 조상은 node2이기 때문에 출력하고 종료함.
        cout<<node2<<endl;
    else
        search(tree,parent,depth+1);
}
void second_search(vector<int>tree[],int first, int depth)
{
    if(tree[first].size()==0) //더이상 부모가 없음.
        return;
    int parent = tree[first][0];
    if(m.find(parent)!=m.end()){ //부모를 찾는 과정에서 map에 있는 원소를 만난다면 그 즉시 출력하고 종료.
    //거꾸로 올라가기에 만나면 그 부모가 가장 가까운 부모가 될 수 밖에 없음.
        cout<<parent<<endl;
        return;
    }
    second_search(tree,parent,depth+1);
}

 

😀느낀 점

• 처음에 생각나는 대로 코드를 짜서, 그렇게 효율적이지 못한 코드인 것 같다.
  • 다른 사람 코드를 보니 재귀함수를 쓰지 않고, while 문을 돌려서 풀었는데, 재귀호출 횟수가 늘어나면 시간복잡도 측면에서 비효율적이기 때문에 while문을 돌려서 푼 것 같다.
• 무조건적인 재귀함수 사용은 다시 한번 생각할 필요성이 있다..

 

자세한 코드 설명은 주석을 통해서 확인해 주세요.