[ SWEA 1248 ] 공통조상 (C++)

SWExpertAcademy의 공통조상(1248 / D5) 문제이다.

[ 문제풀이 ]

1) Tree 형태의 그래프에서 가장 가까운 공통조상을 찾는 문제이다.

   본인은 이 Tree를 구현하기 위해서 구조체를 하나 만들어 주었는데, 구조체에서 관리하는 멤버변수는 다음과 같다.

   { 노드 번호 , 부모노드의 번호 , 2명의 자식 노드의 번호(크기가 2인 배열) , Index }

   이렇게 4개의 변수를 관리해 주었는데, 노드 번호와 부모노드의 번호는 말 그대로 노드들의 번호를 저장하기 위한 변수이다.

   자식 노드의 번호는 2칸짜리 배열로 만들어 주었다. 이진 트리를 기반으로 한 문제이기 때문에 자식이 2명보다 많을 수는

   없기 때문에 2칸짜리 배열로 만들어 주었다. 마지막 Index 변수는 이 자식노드들의 Index를 관리하기 위한 변수이다.

   예를 들어서 입력을 받을 때, '1'번이라는 노드에 '2'번과 '3'번이 순차적으로 자식노드로써 입력이 되었다고 생각해보자.

   즉, 1 2 1 3 ... 이런식으로 입력이 될 때, 첫 번째 자식은 자식 노드의 배열에 0 번 Index에 들어가고 두 번째 자식은

   자식 노드의 배열에 1번 Index에 들어가게 될 것인데, 이 0번 1번을 관리하기 위한 변수이다. (중요치 않은 변수임 !)

   그리고 이 구조체를 배열로써 만들어 주었다. 인덱스 번호가 각 노드의 번호를 의미할 수 있게 10001칸 보다 크게 만들어

   주었다.

  

2) 선언한 구조체 배열에 모두 입력을 받았다면 이제 공통조상을 찾아보자.

   본인은 시작점 2개에서 모두 깊이우선탐색(DFS)을 진행해 주었다. 가장 최상위 부모 노드 까지 갈 때까지 탐색을 하는

   식으로 진행하였다. 이 탐색을 하는 과정에서, 만나는 부모 노드의 번호와 해당 노드까지 가는데 걸리는 시간을

   저장해 주었다.

   이 부분을 위해서 int Dist[10001][2] 라는 배열을 만들어 주었는데 10001의 의미는 노드번호를 의미하고, '2'는 시작점 2

   개를 의미한다. Dist[a][0] = b , Dist[a][1] = c 의 각각의 의미는

   "첫번째 시작점에서 'a'번 노드까지 가는데 걸리는 횟수는 b번입니다." 와 "두번째 시작점에서 'a'번 노드까지 가는데

    걸리는 횟수는 'c'번입니다." 를 의미한다.

    DFS를 탐색하면서 위의 배열에 저장을 시켜주면서 진행한다. 만약 2개의 시작점 모두 탐색을 끝냈다면 ?

    Dist[?][0] , Dist[?][1] 이 2개의 값이 0이 아니고(0 은 방문을 하지 않음을 의미) 가장 최솟값이 가장 가까운 공통조상이

    될 것이다.  

    문제에서 주어진 그림으로 위의 상황을 쉽게 알아보자.

   

      위의 그림에서 8번에서 DFS를 호출 시, Dist 함수를 한번 채워보면 다음과 같아질 것이다.

      Dist[5][0] = 1 , Dist[3][0] = 2 , Dist[1][0] = 3.

      의미를 다시한번 설명하자면, "첫 번째 시작점에서 5번 노드까지 가는데 걸리는 횟수는 1번입니다."

      "첫 번째 시작점에서 3번 노드까지 가는데 걸리는 횟수는 2번입니다." 를 의미한다.

      13번 노드에서 DFS를 호출시 , Dist함수를 한번 채워보면..

      Dist[11][1] = 1, Dist[6][1] = 2, Dist[3][1] = 3, Dist[1][1] = 4 가 될 것이다.

      의미는 생략하겠다.

      즉, Dist 배열에는 2개의 시작점으로부터 갈 수 있는 조상 노드들의 거리가 저장되어 있다.

      따라서, 0이 아니면서, 가장 최솟값이 가장 가까운 공통조상이 될 것이다.

     

3) 위의 과정에 따라서 공통조상을 찾은 후에는 ? 그 공통조상이 이루고 있는 서브트리의 크기를 구해야 한다.

   본인은 이부분을 너비우선탐색(BFS)를 이용해서 구현해 보았다.

   보통 BFS탐색 시, 방문체크가 필수적이지만 이 문제에서 만큼은 필요가 없었다.

   왜냐하면 무조건 자식이 있는 쪽으로 내려가기만 하는 단방향성의 탐색이였기 때문에 방문체크도 필요없이 Count만

   진행해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
#define MAX 10010
#define endl "\n"
using namespace std;
 
struct NODE
{
    int Num;
    int Idx;
    int Parent;
    int Child[2];
};
 
int V, E, Start[2], Answer_Node, SubSize;
int Dist[MAX][2];
NODE Tree[MAX];
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        Tree[i].Num = i;
        Tree[i].Idx = 0;
        Tree[i].Parent = Tree[i].Child[0] = Tree[i].Child[1] = 0;
    }
    memset(Dist, 0, sizeof(Dist));
}
 
void Input()
{
    cin >> V >> E >> Start[0] >> Start[1];
    for (int i = 0; i < E; i++)
    {
        int Parent; cin >> Parent;
        int Child; cin >> Child;
 
        Tree[Parent].Child[Tree[Parent].Idx++] = Child;
        Tree[Child].Parent = Parent;
    }
}
 
void DFS(int Node, int Cnt, int Idx)
{
    Dist[Node][Idx] = Cnt;
    if (Tree[Node].Parent != 0)
    {
        DFS(Tree[Node].Parent, Cnt + 1, Idx);
    }
}
 
int BFS(int N)
{
    queue<int> Q;
    Q.push(N);
    int Cnt = 1;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front();
        Q.pop();
 
        for (int i = 0; i < 2; i++)
        {
            if (Tree[Cur].Child[i] != 0)
            {
                Q.push(Tree[Cur].Child[i]);
                Cnt++;
            }
        }
    }
 
    return Cnt;
}
 
void Solution()
{
    for (int i = 0; i < 2; i++) DFS(Start[i], 0, i);
    
    int Temp_Dist[2] = { 987654321 , 987654321 };
    for (int i = 1; i <= V; i++)
    {
        if (Dist[i][0] != 0 && Dist[i][1] != 0)
        {
            if (Dist[i][0] < Temp_Dist[0] && Dist[i][1] < Temp_Dist[1])
            {
                Temp_Dist[0] = Dist[i][0];
                Temp_Dist[1] = Dist[i][1];
                Answer_Node = i;
            }
        }
    }
 
    SubSize = BFS(Answer_Node);
 
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer_Node << " " << SubSize << endl;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}