(C++) [SWEA 1248] [SW 문제해결 응용] - 3일차 공통조상

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD 

SW Expert Academy

 

문제 요약

이진 트리 1개와 정점 2개가 주어질 때, 주어진 정점 2개의 공통 조상과 공통 조상을 루트로 하는 서브 트리의 크기 출력하기

입출력

테스트 케이스의 수 T가 첫 번째 줄에 주어진다.

이후 각 테스트 케이스 T에 대해 첫 번째 줄에 정점의 수 V, 간선의 수 E, 공통 조상을 찾을 정점 V₁, V₂

가 띄어쓰기 한 칸 을 두고 주어지고, 이후 2*E개에 대해 정점이 띄어쓰기 한 칸을 두고 주어지는데, 이 때 주어진 숫자들은 모두 연결된 간선을 뜻한다. 주어지는 순서는 반드시 부모-자식 순이다.

 

#i(i는 i번째 테스트 케이스를 뜻함) 공통 조상인 정점 공통 조상을 루트로 하는 서브 트리의 크기

순으로 출력한다.

 

접근법

처음에 문제를 봤을 때는 Union-Find인가 싶어서 찾아보니까 Union-Find는 서로소인 집합을 찾는 문제라서, 이 문제는 공통 조상이 존재하므로 쓸 수 없겠다 싶었다.

 

직관적으로 떠오른 방법은 트리를 구성하는 노드에 Parent를 추가해서 공통 조상을 찾아야 하는 노드부터 루트까지 탐색한 다음 겹치는 가장 가까운 부분을 찾는거였는데 정점이 최대 10000개다 보니까 최악의 경우에 테스트케이스 하나당 10000^2개가 걸릴 수 있어서 이 방법은 안 되겠다고 생각했고, 조금 변형해서 풀었다.

 

나는 BFS 방식으로 풀었는데, 방법은 다음과 같다.

(1) 주어진 정점 중  V₁에 대해서 루트까지 탐색 후, 이 정점이 루트까지 가는 과정에서 탐색한 정점들을 

bool 배열에 기록하고,  V₂도 루트까지 탐색하면서 이미 탐색이 완료된 정점이 있다면 해당 정점을 return

없으면 루트를 return

(2) (1)에서 return된 정점을 가지고 BFS로 탐색하면서 (1)을 루트로 하는 모든 정점을 탐색하고, 해당 값을 return

(3) (1),(2)를 출력

 

이 방법은 1번 과정을 수행할 때 O(2*V)이고, 2번 과정에서 O(V)만큼 소요되어서 O(V)만큼의 시간이 걸리므로 시간안에 충분히 풀 수 있을거라고 생각했다.

 

전체 코드는 아래와 같다. (1)은 find() 함수이고, (2)는 search() 함수이다. 

 

#include <iostream>
#include <queue>
using namespace std;
constexpr int MAX = 10002;
typedef struct Node
{
    int data;
    Node* parent, * left, * right;
 
}Node;
int v, e, v1, v2, e1, e2;
int num, treeSize, parent,nodecnt = 1;
bool vis[MAX];
Node nodeArray[MAX];
queue <int> q;
Node* getNode(int data, int parent = 0, int left = 0, int right = 0)
{
    nodeArray[nodecnt].data = data;
    if (parent != 0)
        nodeArray[nodecnt].parent = &nodeArray[parent];
    if (left != 0)
        nodeArray[nodecnt].left = &nodeArray[left];
    if (right != 0)
        nodeArray[nodecnt].right = &nodeArray[right];
    return &nodeArray[nodecnt++];
}
void init()
{
    /* init */
    for (int i = 0; i < MAX; i++)
    {
        nodeArray[i].left = nodeArray[i].right = nodeArray[i].parent = nullptr;
        vis[i] = false;
    }
    num = 0;
    treeSize = nodecnt = 1;
 
    /* input */
    cin >> v >> e >> v1 >> v2;
    for (int i = 1; i <= v; i++)
        getNode(i);
 
    for (int i = 0; i < e; i++)
    {
        cin >> e1 >> e2;
        if (!nodeArray[e1].left)
            nodeArray[e1].left = &nodeArray[e2];
        else
            nodeArray[e1].right = &nodeArray[e2];
        nodeArray[e2].parent = &nodeArray[e1];
    }
    
}
int find(Node* T)
{
    while (T->parent)
    {
        if (vis[T->parent->data])
            return T->parent->data;
        vis[T->parent->data] = true;
        T = T->parent;
    }
    return 1;
}
void search(int start)
{
    for (int i = 0; i < MAX; i++)
        vis[i] = false;
    num = start;
    q.push(start);
 
    while (!q.empty())
    {
        int node = q.front(); q.pop();
 
        if ((nodeArray[node].left && !(vis[nodeArray[node].left->data])))
        {
            q.push(nodeArray[node].left->data);
            vis[nodeArray[node].left->data] = true;
            treeSize++;
        }
        if ((nodeArray[node].right && !(vis[nodeArray[node].right->data])))
        {
            q.push(nodeArray[node].right->data);
            vis[nodeArray[node].left->data] = true;
            treeSize++;
        }
    }
}
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        init();
        find(&nodeArray[v1]);
        search(find(&nodeArray[v2]));
        cout << '#' << i << ' ' << num << ' ' << treeSize << '\n';
    }
}

*틀리거나 잘못된 부분, 혹은 궁금하신 점 있으시면 언제나 댓글 달아주세요!