1월23일 - 경주[BOJ/5820]

문제 설명

주어진 트리는 (N)개의 노드와 (N-1)개의 간선으로 구성되어 있으며, 각 간선은 고유의 길이를 갖는다. 두 도시 사이의 유일한 경로가 존재하도록 트리는 설계되어 있다.

이 문제는 정확히 (K)의 길이를 가지는 경로를 찾는 것이다. 해당 경로는 가능한 적은 수의 간선을 사용해야 하며, 경로가 없을 경우 (-1)을 반환한다.

해결 방법

핵심 아이디어

1. Centroid Decomposition:
   • 트리를 분할 정복 방식으로 분해하며, 각 서브트리에 대해 독립적으로 문제를 해결한다.
2. 거리 기반 동적 계획법:
   • 특정 경로의 길이에 대한 최소 깊이를 저장해 탐색 시간을 절약한다.
3. 서브트리 탐색 최적화:
   • 각 서브트리에서 거리 정보를 효율적으로 갱신하고, 해당 경로가 조건을 만족하는지 확인한다.

코드

#include<bits/stdc++.h> 
using namespace std;
using ll = long long;
const int MAX_NODES = 200000;
const int MAX_DIST = 1000000;
const int INF = 1e9;

int subtree_size[MAX_NODES + 5];
bool is_visited[MAX_NODES + 5];
int min_depth[MAX_DIST + 5];
vector<int> active_distances;
vector<vector<pair<int, int>>> adjacency_list(MAX_NODES + 5);
int node_count, target_length;

// 서브트리의 크기를 계산
int compute_subtree_size(int node, int parent) {
    subtree_size[node] = 1;
    for (const auto& edge : adjacency_list[node]) {
        int neighbor = edge.first;
        if (neighbor == parent || is_visited[neighbor]) continue;
        subtree_size[node] += compute_subtree_size(neighbor, node);
    }
    return subtree_size[node];
}

// 서브트리의 중심 노드를 찾음
int find_centroid(int node, int parent, int threshold) {
    for (const auto& edge : adjacency_list[node]) {
        int neighbor = edge.first;
        if (neighbor == parent || is_visited[neighbor]) continue;
        if (subtree_size[neighbor] > threshold) 
            return find_centroid(neighbor, node, threshold);
    }
    return node;
}

// 특정 경로에 대한 최소 깊이 계산
int compute_min_depth(int node, int parent, int distance, int depth) {
    int result = INF;
    if (distance > target_length) return result;
    result = min(result, min_depth[target_length - distance] + depth);
    for (const auto& edge : adjacency_list[node]) {
        int neighbor = edge.first;
        int weight = edge.second;
        if (neighbor == parent || is_visited[neighbor]) continue;
        result = min(result, compute_min_depth(neighbor, node, distance + weight, depth + 1));
    }
    return result;
}

// 경로 정보를 업데이트
void update_paths(int node, int parent, int distance, int depth) {
    if (distance > target_length) return;
    min_depth[distance] = min(min_depth[distance], depth);
    active_distances.push_back(distance);
    for (const auto& edge : adjacency_list[node]) {
        int neighbor = edge.first;
        int weight = edge.second;
        if (neighbor == parent || is_visited[neighbor]) continue;
        update_paths(neighbor, node, distance + weight, depth + 1);
    }
}

// 분할 정복 알고리즘
int decompose_and_conquer(int node) {
    int threshold = compute_subtree_size(node, -1);
    int centroid = find_centroid(node, -1, threshold / 2);
    is_visited[centroid] = true;
    int result = INF;

    for (const auto& distance : active_distances) 
        min_depth[distance] = INF;

    active_distances.clear();
    min_depth[0] = 0;

    for (const auto& edge : adjacency_list[centroid]) {
        int neighbor = edge.first;
        int weight = edge.second;
        if (!is_visited[neighbor]) {
            result = min(result, compute_min_depth(neighbor, centroid, weight, 1));
            update_paths(neighbor, centroid, weight, 1);
        }
    }

    for (const auto& edge : adjacency_list[centroid]) {
        int neighbor = edge.first;
        if (!is_visited[neighbor]) {
            result = min(result, decompose_and_conquer(neighbor));
        }
    }

    return result;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> node_count >> target_length;
    for (int i = 0; i < node_count - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adjacency_list[u].emplace_back(v, w);
        adjacency_list[v].emplace_back(u, w);
    }

    fill(begin(min_depth), end(min_depth), INF);
    int answer = decompose_and_conquer(0);
    cout << (answer == INF ? -1 : answer) << '\n';

    return 0;
}

코드 설명

주요 함수

1. compute_subtree_size

   • 특정 노드의 서브트리 크기를 계산한다.

2. find_centroid

   • 서브트리의 중심 노드를 찾는다.

3. compute_min_depth

   • 특정 경로에서 목표 길이까지 필요한 최소 깊이를 계산한다.

4. update_paths

   • 현재 노드에서 접근 가능한 경로 정보를 갱신한다.

5. decompose_and_conquer

   • 트리를 중심 노드를 기준으로 분할하고, 각 서브트리에 대해 문제를 해결한다.

So...

이 문제는 트리 분할 정복 알고리즘과 동적 계획법을 결합하여 효율적으로 해결했다. 서브트리 크기를 기반으로 중심 노드를 찾아서 문제를 분할하고, 각 서브트리에 대해 거리와 깊이를 계산했다. 이 과정에서 메모리와 시간을 최적화하는 방법을 사용했으며, 특히 거리 기반 DP가 핵심이었다. 어려운 점은 다양한 경로를 효율적으로 관리하는 것이었으나, 이를 해결하며 깊은 성취감을 느낄 수 있었다.