[개쉬운 풀이] 백준 19542 전단지 돌리기

문제

현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가
D이하인 모든 노드에 전단지를 돌릴 수 있다.

날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.

생각

1. 위 문제는 트리 모양의 길 위에서 진행된다.
2. 따라서 가장 깊은 곳을 방문하고 돌아올때는 x2만 해주면 된다.
3. 또한 현민이는 D이하의 노드는 전단지를 돌릴 수 있다.
4. D이하의 노드는 갈필요가 없다는 뜻이다.
5. 따라서 트리의 깊이를 고려하며 D이하의 자식 노드들은 무시하면 된다.

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

const int MAX = 100001;

int N, S, D;
int ans = 0;

map<int, set<int>> m;  // 그래프를 인접 리스트로 표현 (map을 사용하여 연결된 노드 저장)
int depth[MAX];  // 각 노드의 최대 깊이 저장

void input(){
    cin >> N >> S >> D;  // N: 노드 수, S: 시작 노드, D: 전단지 배부에 필요한 최소 거리
    for(int i = 0; i < N-1; i++){  // N-1개의 간선 정보 입력
        int a,b;
        cin >> a >> b;

        m[a].insert(b);  // a와 b 노드가 서로 연결됨
        m[b].insert(a);  // 양방향 연결
    }
}

// 전단지 배부를 위한 재귀 함수
int process(int x, int before){
    for(auto next : m[x]){  // 현재 노드 x에 연결된 모든 노드 탐색
        if(next == before) continue;  // 이전 노드로 돌아가지 않도록 방지
        depth[x] = max(depth[x], process(next, x)+1);  // 깊이 갱신
    }


    //무조건 방문해야하는 노드들
    if(depth[x] >= D && x != S) ans++;  // 깊이가 D 이상이고 출발점이 아닌 경우 전단지 배부
    return depth[x];
}

void sol(int x){    
    process(x, -1);  // 시작 노드에서 탐색 시작
    cout << ans * 2 << endl;  // 왕복을 고려해 답을 2배 출력
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    input();  // 그래프 입력
    sol(S);  // 시작 노드에서 전단지 배부 처리

    return 0;
}