백준 28019 - 산지니의 여행계획 (C++)

문제

• 문제 링크

  
   BOJ 28019 - 산지니의 여행계획 
  

• 문제 요약

$N$개의 정점으로 이루어진 그래프가 주어지고, 출발점에서 모든 정점을 방문하려 한다.
최대한 도로를 적게 선택 하면서 선택된 도로 길이의 합은 최대가 되기를 원할 때,
모든 여행을 마치기 위한 최소 운전 거리를 구해보자.

• 제한

TL : $1$ sec, ML : $512$ MB




$2 ≤ N ≤ 50,000$

$N - 1 ≤ M, M_w ≤ 1,000,000$

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 깊이 우선 탐색(dfs)
• 최소 스패닝 트리(mst)
• 그리디 알고리즘(greedy)

풀이

$N$개의 도시를 모두 방문 하려 하면서, 도로를 최대한 적게 선택 한다고 한다.
이 대목에서 $MST$ 문제임을 의심해 볼 수 있다.

또한 선택한 도로 길이의 합이 최대가 되기를 원하기 때문에, $Maximum$ $Spanning$ $Tree$ 를 찾아야 한다.
이는 단순히 정렬 기준을 반대로 놓고 $MST$를 구축하면 쉽게 구할 수 있다.

문제는 시작 도시 $m$으로부터 모든 도시를 방문하는 최소 이동 거리를 구해야 한다는 점이다.
주어진 간선에서 $MST$ 구축에 사용된 간선들로 새로이 트리를 만들고 아래 문장을 보자.

"마지막 도시를 방문하면 시작 도시로 돌아가지 않고 그 도시에서 차량을 반납하기로 하였다."

$m$을 루트로 놓고 보면, 결국 가장 먼 지점을 잇는 경로를 마지막에 가는 게 이득임이 자명하다.
또, 이 경로를 제외한 나머지 모든 경로들은 어떤 순서로 방문하던 반드시 두 번 지나치게 된다.

---

다음과 같은 추가 테이블을 하나 정의하자.

$T[i] :$ 시작 정점 $m$을 루트로 하는 트리에서, 정점 $i$와 그 하위 노드 중 가장 멀리 떨어진 지점과의 거리.

이 테이블은 $dfs$ 한 번으로 쉽게 채워 넣을 수 있다.
이때 사용되는 모든 간선의 가중치를 그 두 배 만큼 답에 더해 주자.

최종적으로 답에서 $T[m]$을 빼준 값이 문제의 정답이 되겠다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
vector <tuple<int, int, int>> Eg;
vector <pair<int, int>> Gr[50001];
ll n, m, r, T[50001];
 
int Find(int p) { return T[p] = T[p] == p ? p : Find(T[p]); }
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    iota(T, T + 50001, 0); cin >> n >> m;
    Eg.resize(m);
    for (auto& [w, p, q] : Eg) cin >> p >> q >> w;
    sort(Eg.begin(), Eg.end(), greater<>());
 
    for (auto& [w, p, q] : Eg)
        if (int x(Find(p)), y(Find(q)); x ^ y)
        {
            x > y ? T[x] = y : T[y] = x;
            Gr[p].emplace_back(q, w);
            Gr[q].emplace_back(p, w);
        }
}
ll Solve(int p, int q)
{
    for (auto& [x, y] : Gr[p])
        if (x ^ q)
            T[p] = max(T[p], Solve(x, p) + y), r += y << 1;
    return T[p];
}
int main()
{
    Init();
    memset(T, 0, sizeof T);
    cin >> m;
    Solve(m, m);
    cout << r - T[m];
}

comment

얼마 전 이 문제 에서 비슷한 문제 상황이 있었기에
좀 더 쉽게 접근할 수 있었던 것 같다.