백준 3584 c++

문제

루트가 있는 트리(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 이하의 정수로 이름 붙여집니다.

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

출력

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

예제 입력 1 복사

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

예제 출력 1 복사

4
3

 

#include <bits/stdc++.h>

using namespace std;

int T;
int N;

vector<int>graph[10001];


int visited[10001];
int check[10001];
bool nextcheck = false;


void dfs(int start){


    if(check[start]!=0 && nextcheck==true ){
        cout << start << "\n";
        return;
    }
    visited[start]=1;
    check[start]=1;


    //cout << "current : " << start << "\n";

    for (int i = 0; i <graph[start].size() ; ++i) {
        int next = graph[start][i];
        if(visited[next]==0){
            dfs(next);
        }
    }
}


int main(){

    cin >> T;

    while(T--){
        int A , B;
        int X , Y;

        cin >> N;

        for (int i = 0; i < N-1; ++i) {
            cin >> A >> B;
            graph[B].push_back(A);
        }

        cin >> X >> Y;

        dfs(X);
        nextcheck=true;
        memset(visited,0,10001);
        dfs(Y);
        nextcheck=false;
        memset(check,0,10001);
        memset(visited,0,10001);

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


    }








}

문제를 dfs로 접근해서 풀었으나 계속해서 50%에 실패가 떴다

실패한 코드의 로직은 다음과같다

1. 벡터에 부모와 자식을 넣어준다

2. 첫번째 dfs를 돌리고 부모가 없을때까지 계속 올라간다

3. 방문처리를 계속 해주고 체크처리를 해준다

4. 방문처리를 리셋해주고 처음부터 다시 dfs로 올라간다

5. 만약에 체크된곳에 두번째 dfs가 도착한다면 정답 출력해준다

 

왜 50%에서 에러가 나는지 아시는분은 댓글 부탁드립니다 하핫..

 

그래서 결국 답안을 참고해서 풀이를 했다

 

 

#include <bits/stdc++.h>

using namespace std;

int T;
int N;

int parent[10001];
int visited[10001];


int main(){

    cin >> T;

    while(T--){
        cin >> N;
        int A , B;
        int X, Y;

        for (int i = 1; i <=N ; ++i) {
            visited[i] = 0;
            parent[i]=i;
        }

        for (int i = 1; i <N ; ++i) {
            cin >> A >> B;
            parent[B]=A;
        }

        cin >> X >> Y;
        visited[X] = true;

        while(X!=parent[X]){
            X = parent[X];
            visited[X] = 1;
        }
        while(true){

            if(visited[Y]!=0){
                break;
            }
            Y = parent[Y];
        }
        cout << Y <<"\n";



    }



}

 

 

로직은 틀린 코드와 비슷하다

다만 여기에서는 dfs와 벡터를 사용하지않고

int 배열에 parent를 관리한다

1. visited와 parent를 각각 똑같은 값으로 초기화시켜준다

2. 부모와 자식을 입력받아준다 parent[b]= a;

3. 두개의 노드값을 받아준다

4. 첫번째 노드값에 visited true를 해준다

5. 첫번째값과 parent[첫번째값]이 다를때마다 부모로 찾아 올라간다. 그리고 계속해서 방문처리를 해준다.

6. 만약에 첫번째값과 parent값이 같다는것은 처음에 초기화한 값이므로 루트노드에 온 것을 알 수 있다.

7. while문을 종료하고 다음 while문을 돌린다

8. 두번째값부터 다시 부모를 향해 찾아 올라간다

9. 만약 방문처리가 된곳이면 종료하고 현재 위치값을 출력해준다.