SWEA 1248 공통조상 C++

문제: SW Expert Academy 1248번 공통조상

 

(효율적인 풀이인지 검증이 필요한 풀이입니다)

주어진 트리 정보를 바탕으로, 두 정점의 공통 조상을 파악하고, 그 조상의 자식 노드 수 + 1(=서브 트리 크기)를 구하는 문제이다.

 

개인적으로 트리 문제가 나오면 긴장하는 편인데, 주어진 정보를 바탕으로 트리를 구현해야하나...라는 고민을 처음에 했고, 배열을 이용해서 트리를 구현하려고 했다.

 

하지만 공통조상을 찾기 위해서는 트리를 거슬러 올라가야할 필요가 있었기에 단순히 각 노드의 부모가 누구인지 parent라는 배열에 저장하고, 각 노드의 자식 노드는 누구(들)인지 child라는 2차원 배열에 저장하기로 하였다.

 

이 때 2차원 배열인 이유는, 주어진 트리가 이진 트리이기 때문인데, 그냥 vector를 이용하여 구현하였다.

 

위와 같이 단순히 트리를 구현한 이후에는, 공통 조상을 찾아야하는 대상인 두 노드 s(source)와 d(destination)중 하나인 s의 부모의 부모의 부모...를 찾아가며, 매번 그 조상의 자손 중에 d가 존재하는지 파악하고자 하였고 이는 dfs로 구현하였다.

 

이런 방법으로 공통 조상을 찾은 후에는, 서브 트리의 크기를 구해야 했고, 이 또한 dfs를 이용하였다.(함수의 이름은 subtree_size이다.)

 

반복적인 dfs 적용으로 굉장히 단순하게 풀었는데, 분명 더 나은, 더 고차원적인 방법이 있을 것 같다.

 

관련 내용은 이후에 포스팅해볼 수 있도록 하겠다.

 

/* SWEA 1248 공통조상 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int t, T, v, e, s, d, cnt;
int parent[10001], visited[10001];
vector<int> child[10001];
bool found = false;
 
void dfs(int node)
{
    if (node == d)
    {
        found = true;
        return;
    }
 
    if (visited[node])
        return;
 
    visited[node] = true;
    for (int c : child[node])
    {
        if (!visited[c] || !found)
            dfs(c);
    }
}
 
void subtree_size(int node)
{
    if (visited[node])
        return;
 
    visited[node] = true;
    cnt++;
 
    for (int c : child[node])
        if (!visited[c])
            subtree_size(c);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cin >> T;
    for (t = 1; t <= T; t++)
    {
        found = false, cnt = 0;
        memset(visited, 0x00, sizeof(visited));
        memset(child, 0x00, sizeof(child));
        memset(parent, 0x00, sizeof(parent));
 
        cin >> v >> e >> s >> d;
 
        for (int i = 0; i < e; i++)
        {
            int p, c;
            cin >> p >> c;
            // c의 부모는 p이고, p의 자식은 c이다
            parent[c] = p;
            child[p].push_back(c);
        }
 
        /*for (int i = 1; i <= v; i++)
            cout << parent[i] << ' ';
        cout << endl;*/
 
        // 공통 조상 찾기
        int tmp_p = s;
        int common_parent = 0;
        while (tmp_p != 0)
        {
            tmp_p = parent[tmp_p]; // 조상을 하나씩 거슬러 올라가기
            
            dfs(tmp_p); // 해당 조상의 자손 중에 d가 있다면 공통조상 찾은 것
            
            if (found) // 공통 조상 찾음
            {
                common_parent = tmp_p;
                break; // 탐색 중단
            }
        }
 
        memset(visited, 0x00, sizeof(visited)); // 서브트리 크기 구하기 위해 방문 배열 초기화
        subtree_size(common_parent); // 서브트리 크기 구함
 
        cout << "#" << t << " " << common_parent << " " << cnt << endl;
    }
 
    return 0;
}