백준 3584 가장 가까운 공통 조상 C++

문제

https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

문제 풀이

1) 양방향 데이터로 담지않고 단방향 데이터로 담는다. 자식->부모로 거슬로 올라가는 정보를 담는다.

2) 문제에서 주어진 정점의 부모들을 unordered_map 에 담는다. 이때 unordered_map 의 value 가 0 이 아니면 공통 조상이기 때문에

해당 정점을 출력해준다.

3) unordered_map에는 자기 자신부터 담겨야한다.

 

코드

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int t, n, parentVertex, childVertex, vertex1, vertex2, ans;
vector<int> adj[10001]; //curVertex
unordered_map<int, int> m; //parentVertex, cnt

void getParentVertex(int vertex) {
    for(int i = 0; i < adj[vertex].size(); i++) {
        int parentVertexTemp = adj[vertex][i];
        if(m[parentVertexTemp] == 0) {
            m[parentVertexTemp]++;
            getParentVertex(adj[vertex][i]);
        } else {
            ans = parentVertexTemp;
            return;
        }
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n - 1; i++) {
            cin >> parentVertex >> childVertex;
            adj[childVertex].push_back(parentVertex);
        }

        cin >> vertex1 >> vertex2;
        m[vertex1]++;
        m[vertex2]++;
        getParentVertex(vertex1);
        getParentVertex(vertex2);

        cout << ans << "\n";

        for(int i = 0; i < 10001; i++) {
            adj[i].clear();
        }
        m.clear();
    }

	return 0;
}

 

해당 문제를 풀고 다른 사람들의 문제를 검색해보니

가장 가까운 공통 조상(Nearest Common Anscestor) 문제 유형이라고 한다.

 

다음에는 가장 가까운 공통 조상(Nearest Common Anscestor 알고리즘을 이용하여 풀어봐야겠다.