[Baekjoon] 3584번: 가장 가까운 공통 조상

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

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

 

1. parent 배열에  parent[자식] = 부모   (parent[m] = n) 자신의 바로 위 부모를 저장한다.

2. u, v 값을 받아 가장 가까운 공통 부모를 찾는데, 먼저 u에서 DFS로 자신의 위에있는 부모를 방문하고 , isVisited를 true로 표시한다.

3. 방문 후, v를 DFS 했을때, 가장 처음 만나는 isVisited가 true인 노드가 u와 v의 가장 가까운 부모(조상)이다. 

 

 

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

int parent[10001];
bool isVisited[10001];
int answer = 0;
void DFS(int V){
   
    if(isVisited[V] == true) {answer = V; return;}
    isVisited[V] = true;
    
    DFS(parent[V]);
}
int main()
{
    int N,T, n,m, u,v;
    cin >> N;
    while (N--) {
        cin >> T;
        memset(parent, 0, 10001*sizeof(int));
        memset(isVisited, false, 10001*sizeof(bool));
        
        for(int t=0;t<T-1;t++){
            cin >> n >> m;
            parent[m] = n;
        }
        cin >> u >> v;
        DFS(u);
        DFS(v);
        
        cout << answer << "\n";
    }
    
    return 0;
}

---

 

📖후기

parent와 isVisited를 처음에 벡터가 아닌 배열로 풀었더니, 메모리 초과 문제가 발생했다.
앞으로 문제를 풀때 시간과 메모리를 신경쓰며 풀어야겠다!

https://sueaty.tistory.com/59님의 블로그를 참고했습니다!