루오구 P2537 스키 문제: 유향 그래프에서 최소 신장 트리 활용 전략

루오구 P2537 스키 문제는 여러 산봉우리 중 1번 산에서 출발하여, 자신보다 낮은 산으로만 스키를 타고 이동할 수 있습니다. 또한, '물약'을 사용하여 이전에 방문했던 어떤 산으로든 되돌아갈 수 있습니다. 이 문제의 목표는 1번 산에서 도달 가능한 모든 산을 방문하는 데 드는 최소 총 비용을 계산하는 것입니다.

문제 분석 및 접근 방식

스키를 타는 것은 높은 산에서 낮은 산으로만 가능하므로, 각 산 사이의 이동은 방향성을 가집니다. 하지만 물약을 통해 이미 방문한 산 사이에서는 자유롭게 이동할 수 있다는 조건은 사실상 방문된 정점들 사이의 연결성을 보장합니다. 즉, 우리가 1번 산에서 도달 가능한 모든 산봉우리를 연결하기 위한 최소 비용을 찾는 문제로 해석할 수 있습니다. 이는 전형적인 최소 신장 트리(Minimum Spanning Tree, MST) 문제의 형태를 띠지만, 유향 그래프라는 점이 특별한 고려를 필요로 합니다.

문제 해결은 크게 두 부분으로 나눌 수 있습니다:

  1. 1번 산에서 도달 가능한 모든 산의 개수를 세고, 어떤 산들이 도달 가능한지 표시합니다.
  2. 도달 가능한 산들만을 대상으로, 주어진 규칙에 따라 최소 비용으로 모든 산을 연결합니다.

도달 가능한 정점 탐색 (BFS)

먼저, 1번 산에서 시작하여 스키를 탈 수 있는 모든 경로를 따라 너비 우선 탐색(BFS)을 수행합니다. 이 BFS는 visited_bfs 배열을 채워 1번 산에서 도달 가능한 모든 산을 표시합니다. 이 과정에서 발견된 산의 개수가 첫 번째 출력 값(reachable_count)이 됩니다. BFS에서 사용되는 간선은 높이 조건(현재 산의 높이 >= 다음 산의 높이)을 만족하는 모든 간선이며, 양방향으로 연결될 수 있는 경우 모두 고려하여 모든 가능한 도달 경로를 찾습니다.

int calculate_reachable_nodes_count(int start_node, int num_nodes, const std::vector<std::pair<int, int>> adj_for_bfs[], bool visited_bfs[]) {
    int count = 0;
    std::queue<int> q;

    q.push(start_node);
    visited_bfs[start_node] = true;
    count++;

    while (!q.empty()) {
        int current_node = q.front();
        q.pop();

        for (const auto& edge : adj_for_bfs[current_node]) {
            int neighbor = edge.first;
            if (!visited_bfs[neighbor]) {
                visited_bfs[neighbor] = true;
                q.push(neighbor);
                count++;
            }
        }
    }
    return count;
}

간선 구성 및 정렬

모든 가능한 스키 이동 경로(높이가 높은 곳에서 낮은 곳으로의 이동)를 나타내는 간선들을 수집합니다. 이때, 각 간선은 (출발 정점 u, 도착 정점 v, 비용 weight)의 형태를 가집니다. 문제의 핵심은 이 간선들을 어떻게 정렬하여 MST 알고리즘에 적용하느냐에 있습니다.

크루스칼(Kruskal) 알고리즘은 일반적으로 무향 그래프에 사용됩니다. 유향 그래프에서 단순히 비용이 적은 간선부터 선택하는 방식은 올바른 '최소 연결'을 보장하지 않습니다. 예를 들어, A → B (비용 1), B → C (비용 2)가 있고 A → C (비용 100)가 있을 때, 크루스칼은 비용 1과 2의 간선을 선택하여 A, B, C가 연결되었다고 판단하지만, 유향 그래프에서는 C에서 A로는 갈 수 없습니다. 하지만 이 문제에서는 물약 사용 조건과 특정 정렬 기준 덕분에 크루스칼 알고리즘을 변형하여 적용할 수 있습니다.

간선 정렬 기준:

  1. 도착 정점(v)의 높이(heights[v])가 높은 순서대로: 이는 우리가 낮은 산을 먼저 연결하여 전체적인 연결 구조를 만들어나가는 데 도움이 됩니다. 스키는 높은 곳에서 낮은 곳으로만 탈 수 있으므로, 낮은 산을 먼저 고려하면 그 산에 도달하기 위해 필요한 경로를 효율적으로 구성할 수 있습니다.
  2. 만약 도착 정점의 높이가 같다면, 간선의 비용(weight)이 낮은 순서대로: 이는 크루스칼 알고리즘의 기본적인 그리디(탐욕) 선택 원칙을 따릅니다.

이 특별한 정렬 방식은, 물약을 통해 되돌아갈 수 있다는 조건과 결합되어, 유향 그래프 문제를 무향 그래프처럼 연결성 관점에서 처리할 수 있게 합니다. 즉, '연결'만 되면 물약으로 오갈 수 있으니, 최소 비용으로 모든 도달 가능한 산을 연결하는 것이 목표가 됩니다.

struct SkiEdge {
    int u, v, weight; // u: 출발, v: 도착, weight: 비용
};

// ... (main 함수 내 또는 전역)
std::vector<SkiEdge> all_potential_edges;
// ... 간선 구성 로직 (heights[u] >= heights[v] 또는 heights[v] >= heights[u]인 경우 모두 all_potential_edges에 추가)

std::sort(all_potential_edges.begin(), all_potential_edges.end(), [&](const SkiEdge& a, const SkiEdge& b) {
    if (heights[a.v] != heights[b.v]) {
        return heights[a.v] > heights[b.v]; // 도착 정점의 높이가 높은 순서대로
    }
    return a.weight < b.weight; // 높이가 같으면 비용이 낮은 순서대로
});

최소 비용 경로 계산 (Kruskal 응용)

정렬된 간선들을 사용하여 크루스칼 알고리즘을 적용합니다. 이 과정에서 유니온-파인드(Union-Find) 자료구조를 활용하여 두 정점이 이미 연결되어 있는지 확인하고, 연결되어 있지 않다면 두 정점을 연결하고 해당 간선의 비용을 누적합니다. 중요한 점은, BFS에서 도달 가능하다고 판별된 정점들만을 대상으로 이 작업을 수행해야 한다는 것입니다. visited_bfs 배열이 이 필터링 역할을 합니다.

// Union-Find 자료구조
std::vector<int> parent;
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

// ... (main 함수 내)
long long min_total_cost = 0;
for (const auto& edge : all_potential_edges) {
    // 1번 산에서 도달 불가능한 출발 정점은 건너뛴다.
    // 이는 BFS의 visited_bfs 배열로 필터링된다.
    if (!visited_bfs[edge.u]) {
        continue;
    }

    int root_u = find_set(edge.u);
    int root_v = find_set(edge.v);

    if (root_u != root_v) {
        union_sets(root_u, root_v);
        min_total_cost += edge.weight;
    }
}

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <numeric> // For std::iota

const int MAX_NODES = 1000005;

struct SkiEdge {
    int u, v, weight;
};

// Node heights
int heights[MAX_NODES];
// For Union-Find
std::vector<int> parent;
// For BFS reachability check
bool visited_bfs[MAX_NODES];
// Adjacency list for BFS (all valid downhill/uphill moves initially)
std::vector<std::pair<int, int>> adj_for_bfs[MAX_NODES];

// Union-Find find operation
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

// Union-Find union operation
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

// BFS to find all reachable nodes from start_node
int calculate_reachable_nodes_count(int start_node, int num_nodes, const std::vector<std::pair<int, int>> adj_for_bfs[], bool visited_bfs[]) {
    int count = 0;
    std::queue<int> q;

    q.push(start_node);
    visited_bfs[start_node] = true;
    count++;

    while (!q.empty()) {
        int current_node = q.front();
        q.pop();

        for (const auto& edge : adj_for_bfs[current_node]) {
            int neighbor = edge.first;
            if (!visited_bfs[neighbor]) {
                visited_bfs[neighbor] = true;
                q.push(neighbor);
                count++;
            }
        }
    }
    return count;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_nodes, num_edges;
    std::cin >> num_nodes >> num_edges;

    // Initialize Union-Find parent array
    parent.resize(num_nodes + 1);
    std::iota(parent.begin(), parent.end(), 0);

    for (int i = 1; i <= num_nodes; ++i) {
        std::cin >> heights[i];
    }

    std::vector<SkiEdge> all_potential_edges;
    for (int i = 0; i < num_edges; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;

        // Add edges where height difference allows movement
        // For BFS: add both directions if valid for reachability
        // For MST: all_potential_edges will store these directed edges
        if (heights[u] >= heights[v]) {
            adj_for_bfs[u].push_back({v, w}); // Downhill
            all_potential_edges.push_back({u, v, w});
        }
        if (heights[v] >= heights[u]) {
            adj_for_bfs[v].push_back({u, w}); // Uphill (for BFS reachability check if valid)
            all_potential_edges.push_back({v, u, w});
        }
    }

    // Step 1: Find reachable nodes from mountain 1
    int reachable_count = calculate_reachable_nodes_count(1, num_nodes, adj_for_bfs, visited_bfs);

    // Step 2: Sort edges for Kruskal's algorithm
    std::sort(all_potential_edges.begin(), all_potential_edges.end(), [&](const SkiEdge& a, const SkiEdge& b) {
        if (heights[a.v] != heights[b.v]) {
            return heights[a.v] > heights[b.v]; // Sort by destination height descending
        }
        return a.weight < b.weight; // Then by weight ascending
    });

    // Step 3: Apply Kruskal's to calculate minimum cost
    long long min_total_cost = 0;
    for (const auto& edge : all_potential_edges) {
        // Only consider edges originating from a node reachable from mountain 1
        // and forming a path for the MST
        if (!visited_bfs[edge.u]) {
            continue; // If the source node is not reachable, this edge cannot be part of our solution path
        }

        int root_u = find_set(edge.u);
        int root_v = find_set(edge.v);

        if (root_u != root_v) {
            union_sets(root_u, root_v);
            min_total_cost += edge.weight;
        }
    }

    std::cout << reachable_count << " " << min_total_cost << std::endl;

    return 0;
}

태그: 최소신장트리 크루스칼알고리즘 그래프이론 너비우선탐색 유니온파인드

11월 5일 10:18에 게시됨