[boj : 8012]한동이는 영업사원!

[문제] : https://www.acmicpc.net/problem/8012

8012번: 한동이는 영업사원!

[분류] : LCA 알고리즘

 

[조건]:

가장 핵심적이고 중요한 조건은 "도로끼리 사이클을 만들지 않는다."입니다.

이 문장은 사이클이 발생하지 않는 그래프라는 뜻이며 이는 즉,"트리"임을 암시합니다.

이 조건을 빨리 파악하면 문제를 쉽게 접근 할 수 있게 됩니다.

 

[구현 방법]:

먼저 이 문제를 풀려면 "LCA 알고리즘"의 개념에 대해 습득이 되어 있어야 되는 상태입니다.

(https://www.crocus.co.kr/660)

LCA(Lowest Common Ancestor) 알고리즘

(감사합니다)

우선 트리임을 파악하고 서로 다른 노드의 거리를 구하는 문제는 lca 알고리즘의 전형적인 문제 유형이라고 생각하면 되겠습니다.한 노드와 한 노드 사이의 이동하는데 걸리는 시간은 1 이므로 노드의 depth를 가지고 답을 도출 해 낼 수 있습니다.

a 노드의 depth와 b 노드의 depth를 일단 맞추어 주고(맞추어 주는 과정에서 거리를 더해줍니다.) 두 노드의 lca를 구한 다음 a 또는 b 노드의 depth에서 lca 노드의 depth를 빼준 값을 더해주면 바로 답이 됩니다. 

 

[소스]:

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#define SIZE 30000
 
using namespace std;
 
int n, m, max_size;
 
int ac[SIZE + 1][20], depth[SIZE + 1];
vector<int> v[SIZE + 1];
void dfs(int cur, int par);
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int a, b, ans = 0;
    cin >> n;
    max_size = (int)floor(log2(SIZE));
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    depth[0] = -1;
    dfs(1, 0);
 
    int x = 1, y, tmp;
    cin >> m;
    while (m--)
    {
        cin >> y;
        tmp = y;
        if (depth[x] != depth[y])
        {
            if (depth[x] > depth[y])
                swap(x, y);
            for (int i = max_size; i >= 0; i--)
            {
                if (depth[x] <= depth[ac[y][i]])
                {
                    ans += depth[y] - depth[ac[y][i]];
                    y = ac[y][i];
                }
            }
        }
        int lca = x, pre = y;
        if (x != y)
        {
            for (int i = max_size; i >= 0; i--)
            {
                if (ac[x][i] != ac[y][i])
                {
                    x = ac[x][i];
                    y = ac[y][i];
                }
                lca = ac[x][i];
            }
            ans += 2 * (depth[pre] - depth[lca]);
        }
        x = tmp;
    }
    cout << ans;
    return 0;
}
void dfs(int cur, int par)
{
    depth[cur] = depth[par] + 1;
    ac[cur][0] = par;
    for (int i = 1; i <= max_size; i++)
        ac[cur][i] = ac[ac[cur][i - 1]][i - 1];
 
    for (auto u : v[cur])
    {
        if (u != par)
            dfs(u, cur);
    }
}

#어색한 표현이나 설명이 틀린부분 그리고 필요 없는 코드가 존재한다면 언제라도 태클 걸어주시면 감사하겠습니다