[알고리즘] 정올 1440 번 문제 : 가까운 공통 조상 찾기

이번에는 루트가 있는 트리 구조와 노드 찾기에 대한 알고리즘 문제를 소개합니다.

 

1. 문제 이해

문제 제목과 같이 미로찾기 문제이고 이동할 수 있는 최대 거리를 구해야 합니다.

이동한 지점에서 각 방향으로 가능한 경로를 확인하면서 탐색해봐야 할 것 같습니다.

 

문제는 아래에서 확인하시고 충분히 읽어보시길 바랍니다.

정올 1440 문제

JUNGOL

 

2. 입력 방식 확인

이 문제는 입력 받은 데이터를 트리구조로 잘 만들어줄 필요가 있다.

입력 방식을 확인하면서 어떤 자료 구조로 받는게 좋을까를 고민해보자

 

입력데이터는 더보기 ↓클릭↓

16    //! Node 갯수 16, 15개(N-1)의 두개의 정수
1 14  //! [1] 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 //! [15] Node-1 갯수 만큼 입력된다.
16 7  //! 가장 가까운 공통 조상을 알고 싶은 두 개의 노드

 

3. 그래프 그려보기

그래프 노드 문제는 코딩을 하기 전에 그려보는 것이 도움이 됩니다.

그래프는 종이에 그려도 되고, 툴을 이용해보는 것도 좋겠습니다.

※ 종이에 직접 그리는 게 더 빠를 수 있지만, 자료를 만들고 포스팅을 하려고 하니 draw.io 와 같은 툴을 사용했습니다.

 

입력데이터는 다음과 같은 그래프가 될 것입니다.

draw.io 에서 그려본 입력데이터

 

 

마지막 입력받은 두 개의 노드의 가장 가까운 공통 조상은 아래와 같게 됩니다.

16과 7의 공통 조상

4. 전역변수 선언

입력받은 데이터를 Super Node 와 Sub Node 형태의 그래프로 구현하기 위해서는 연속된 데이터를 처리할 수 있고 탐색을 할 수 있어야 겠습니다.

 

자료구조에 대해서도 이 블로그에서 포스팅을 할 예정이지만, Vector 형태로 데이터를 받고 양방향으로 탐색을 하기 위해서 다음과 같은 전역변수를 선언합니다.

※ 반드시 전역변수를 선언할 필요는 없지만, 문제 풀이시 편의를 위해 전역으로 선언하겠습니다.

#define MAX (10001)
vector <int> gNode[MAX];
vector <int> revNode[MAX];

 

5. 데이터 입력받기

테스트를 위해서 아래 구문을 추가하면, txt file 형태로 input 을 처리할 수 있습니다.

freopen("input.txt", "r", stdin);

두 개의 노드에 대해서 Vector 형태로 선언하여 양방향 저장하고, 각 노드에 대해서 Depth 관리를 위한 변수 선언

    int N;
    scanf("%d ", &N);

    vector <int> gDepth(N + 1, 0); //! N의 Node 의 depth 관리를 위해 선언
    int a, b;

    for (int i = 1; i < N; i++) {
       scanf("%d %d ", &a, &b);
       gNode[a].emplace_back(b);   //! a --> b
       gDepth[b]++;                //! b 는 a 의 자식이므로 depth 를 증가시켜준다.
       revNode[b].emplace_back(a); //! b --> a
    }

    scanf("%d %d ", &a, &b);

 

6. 가까운 조상 찾기

1. revNode 를 이용하여 각 Node 로 부터 상위 부모 Node 로 올라가면서 서로 일치하는지 확인한다.

※ 이 때, 한 쪽이 먼저 올라가면 Depth 가 다르면, 같은 조상이 있더라도 동시에 비교가 어려울 것이다.

 

코드는 더보기 ↓클릭↓

    bool end_cond = true;

    //! Find Super Node
    while (end_cond)
    {
        //printf("%d %d\n", tmpA, tmpB);

        if (tmpA == tmpB)
        {
            end_cond = false;
        }
        else
        {
            tmpA = revNode[tmpA][0];
            tmpB = revNode[tmpB][0];
        }
    }

 

2. Node 검색 전에 출발 Depth 을 맞춰주는 작업이 필요하다.

코드는 더보기 ↓클릭↓

    //! Sync Depth
    int tmpA = a, tmpB = b;
    if (gDepth[a] > gDepth[b]) {
        while (gDepth[tmpA] != gDepth[b]) {
            tmpA = (int)revNode[tmpA][0];
        }
    }

    if (gDepth[a] < gDepth[b]) {
        while (gDepth[a] != gDepth[tmpB]) {
            tmpB = (int)revNode[tmpB][0];
        }
    }

 

여기까지 정리를 하겠습니다.

전체 코드를 추가해놓지 않아서 문제 풀이가 모두 제공된 건 아니지만, 한번 풀어보시고 필요하시면 댓글로 문의 주세요.