[백준,c++] 19542번 - 전단지 돌리기

문제

19542번: 전단지 돌리기

 

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int>graph[100001];
int depth[100001];
int N, S, D, ans = 0;


int dfs(int node, int before){
    for(auto next: graph[node]){
        if(next != before){
            depth[node] = max(depth[node], dfs(next, node)+1);  // 각 노드의 깊이 자손들 중 가장 깊은 노드의 깊이를 알 수 있음
        }
    }
    if(depth[node]>=D && node != S) ans++;
    return depth[node];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>S>>D;
    for(int i=0; i<N-1; i++){
        int a,b; cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    dfs(S, -1);
    
    cout<<ans*2;
    
}

 

풀이

입력에서 노드의 개수가 100,000까지 들어오기 때문에 dfs를 한 번만 돌아서 풀어야 해결해야 하는 문제입니다.

이 문제는 위 코드의 이 부분이 가장 핵심 로직입니다.

depth[node] = max(depth[node], dfs(next, node)+1);  // 각 노드의 깊이 자손들 중 가장 깊은 노드의 깊이를 알 수 있음

위 로직을 돌게되면 depth는 위 이미지와 같이 저장되게 됩니다.

• depth[node]는 각 노드 아래로 연결된 노드들 중 가장 길게 연결된 노드의 길이를 의미합니다.
• 2번 노드의 경우는 3번과 4번 두 개가 연결되어 있지만, 3번 노드가 5, 6번 노드 두 개를 가지게 되어 4번 노드보다 길어져 2번 노드의 depth는 3번 노드를 포함한 3이 됩니다.

depth[node]가 D이상이 되면 해당 노드는 필수로 방문해야 하기 때문에 ans++을 해줍니다. (첫 번째 시작점으로 이동해야 하는 거리가 아니기에 포함하지 않습니다.)

그 후 왕복을 하는 것이기에 ans *2를 하여 출력합니다.