루오구 P2537 스키 문제는 여러 산봉우리 중 1번 산에서 출발하여, 자신보다 낮은 산으로만 스키를 타고 이동할 수 있습니다. 또한, '물약'을 사용하여 이전에 방문했던 어떤 산으로든 되돌아갈 수 있습니다. 이 문제의 목표는 1번 산에서 도달 가능한 모든 산을 방문하는 데 드는 최소 총 비용을 계산하는 것입니다.
문제 분석 및 접근 방식
스키를 타는 것은 높은 산에서 낮은 산으로만 가능하므로, 각 산 사이의 이동은 방향성을 가집니다. 하지만 물약을 통해 이미 방문한 산 사이에서는 자유롭게 이동할 수 있다는 조건은 사실상 방문된 정점들 사이의 연결성을 보장합니다. 즉, 우리가 1번 산에서 도달 가능한 모든 산봉우리를 연결하기 위한 최소 비용을 찾는 문제로 해석할 수 있습니다. 이는 전형적인 최소 신장 트리(Minimum Spanning Tree, MST) 문제의 형태를 띠지만, 유향 그래프라는 점이 특별한 고려를 필요로 합니다.
문제 해결은 크게 두 부분으로 나눌 수 있습니다:
- 1번 산에서 도달 가능한 모든 산의 개수를 세고, 어떤 산들이 도달 가능한지 표시합니다.
- 도달 가능한 산들만을 대상으로, 주어진 규칙에 따라 최소 비용으로 모든 산을 연결합니다.
도달 가능한 정점 탐색 (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로는 갈 수 없습니다. 하지만 이 문제에서는 물약 사용 조건과 특정 정렬 기준 덕분에 크루스칼 알고리즘을 변형하여 적용할 수 있습니다.
간선 정렬 기준:
- 도착 정점(v)의 높이(
heights[v])가 높은 순서대로: 이는 우리가 낮은 산을 먼저 연결하여 전체적인 연결 구조를 만들어나가는 데 도움이 됩니다. 스키는 높은 곳에서 낮은 곳으로만 탈 수 있으므로, 낮은 산을 먼저 고려하면 그 산에 도달하기 위해 필요한 경로를 효율적으로 구성할 수 있습니다. - 만약 도착 정점의 높이가 같다면, 간선의 비용(
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;
}