이번 문제는 DFS를 통한 그래프 탐색으로 해결하였다. 결과적으로 현재 위치에서 갈 수 있는 최대 깊이-현재 위치의 깊이>=d인 위치까지 가면 모든 노드에 전단지를 돌릴 수 있게된다.

• 경로들을 vector배열로 저장해준다.
• 각 노드에서의 깊이와 최대 깊이를 나타내기 위한 depth와 maxDepth를 선언한다.
• 경로는 양방향이므로 양방향으로 저장해준다.
• DFS함수를 통해 그래프 탐색을 한다. 이때 내부에서 다음 노드의 깊이를 정의해주고, 재귀호출한다. 이 과정에서 최대 깊이가 구해진다.
• 최대깊이-현재깊이가 d보다 크거나 같다면 cnt에 2를 더해준다. 2를 더하는 이유는 경로를 다시 돌아와야 하기 때문이다.
• cnt가 2보다 크거나 같다면 cnt-2를 출력해주고, 작다면 0을 출력해준다. 이는 s가 최소 1이기 때문이다. (1이 아닌 2인 이유는 왕복을 고려해야 하기 때문이다.)

이 코드를 처음에 실행하였을 때,

maxDepth=depth=vector<int>(n+1, 0);
depth[s]=1;

이 부분에서 maxDepth=depth=vector<int>(n+1, 0);를 작성하지 않아 에러가 발생하였다. depth[s]가 bad access라는 내용이었다. 곰곰히 생각해보니, vector는 queue나 stack처럼 차곡차곡 쌓는 구조인데 depth에 대한 값들이 하나도 들어가 있지 않은 상태에서 s라는 인덱스를 요구했기 때문이었다. vector를 사용하는데 주의해야 할 부분이라고 생각했다.

Code

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;

int n,s,d;
vector<int> road[MAX];
vector<int> depth;
vector<int> maxDepth;
int cnt=0;

void Input(){
    cin>>n>>s>>d;
    for(int i=0; i<n-1; i++){
        int a,b;
        cin>>a>>b;
        road[a].push_back(b);
        road[b].push_back(a);
    }
}

int DFS(int cur){
    int result=depth[cur];
    for(int i=0; i<road[cur].size(); i++){
        int des=road[cur][i];
        if(!depth[des]){
            depth[des]=depth[cur]+1;
            result=max(result, DFS(des));
        }
    }
    maxDepth[cur]=result;
    if(maxDepth[cur]-depth[cur]>=d){
        cnt+=2;
    }
    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    maxDepth=depth=vector<int>(n+1, 0);
    depth[s]=1;
    DFS(s);
    if(cnt-2>=0)
        cout<<cnt-2<<endl;
    else
        cout<<0<<endl;
    return 0;
}