백준 10623 - Breadth-First Search by Foxpowe (C++)

문제

• 문제 링크

  
   BOJ 10623 - Breadth-First Search by Foxpowe 
  

• 문제 요약

$N$개의 노드로 이루어진 트리가 주어진다.
$1$부터 $BFS$를 진행할 시 방문되는 노드의 순서대로 이동할 때, 총 이동 거리를 계산하자.


• 제한

TL : $2$ sec, ML : $128$ MB




$1 ≤ N ≤ 10^5$

루트 노드는 $1$이다.

알고리즘 분류

• 그래프 이론 (graphs)
• 그래프 탐색 (graph_traversal)
• 너비 우선 탐색 (bfs)
• 트리 (trees)
• 최소 공통 조상 (lowest common ancestor)

풀이

어려울 것 없이, 문제의 요구 사항을 그대로 구현해주면 된다.
단, $N ≤ 10^5$ 이므로 이동 거리를 나이브하게 계산할 순 없으니, $LCA$를 이용해 두 노드 사이 거리를 $O(logN)$에 구하도록 하자.

우선 $1$번 노드로부터 $BFS$를 돌려보며 큐에서 꺼내지는 순서대로 기록해두자.
또, 간선의 가중치를 $1$로 잡고 $LCA$를 위한 전처리를 진행하자.

이제 $now = 1$로 잡고, 다음 이동할 정점을 $rec[i]$라 한다면 $dist_{now} + dist_{rec[i]} - 2 * dist_{lca(now, rec[i])}$ 로 이동 거리를 누적할 수 있다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <int> Gr[N];
int dep[N], dist[N], dp[N][18];
int n, rec[N];
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i(2); i <= n; i++)
    {
        int par; cin >> par;
        Gr[par].push_back(i);
    }
}
void BFS()
{
    queue <int> Q; Q.push(1);
    for (int cnt{}; Q.size();)
    {
        int& now(Q.front()); Q.pop();
        rec[cnt++] = now;
 
        for (int& nxt : Gr[now])
            Q.push(nxt);
    }
}
void LCAInit(int now, int depth)
{
    dep[now] = depth;
    for (int& nxt : Gr[now])
        if (!dep[nxt])
        {
            dist[nxt] = dist[now] + 1;
            dp[nxt][0] = now;
 
            LCAInit(nxt, depth + 1);
        }
}
void TableDP()
{
    for (int j(1); j < 18; j++)
        for (int i(1); i <= n; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int getLCA(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    int diff(dep[x] - dep[y]);
 
    for (int i{}; diff; diff >>= 1, i++)
        if (diff & 1)
            x = dp[x][i];
    if (x ^ y)
    {
        for (int i(17); !!~i; i--)
            if (dp[x][i] ^ dp[y][i])
                x = dp[x][i], y = dp[y][i];
        x = dp[x][0];
    }
    return x;
}
void getAns()
{
    long long ans{};
    for (int i(1), now(1); i < n; i++)
    {
        int lca(getLCA(now, rec[i]));
        ans += dist[now] + dist[rec[i]] - 2 * dist[lca];
        now = rec[i];
    }
    cout << ans;
}
int main()
{
    Input();
    BFS();
    LCAInit(1, 1);
    TableDP();
    getAns();
}

comment

끝