[코드트리] 정점 순회 C++

며칠 동안 고민하다가, 계속 고민해도 답이 없을 것 같아서 해설을 봤다.

문제의 핵심은 리프노드로부터 거리가 d이상인 노드는 무조건 방문해야 한다는 것이다.

 

아래의 두 문장을 보고, 문제의 핵심을 다시 보면 조금 이해될 수도 있다.

거리가 d인 노드를 방문하면 리프노드까지 칠해진다.

해당 노드를 방문했다면 해당 노드에서 루트노드까지의 경로는 무조건 방문되어야 한다(점프해서 방문할 수는 없으니까)

 

나는 색칠한다는 관점에서만 생각했다.

리프노드로부터 d거리에 있는 노드를 방문해야 한다는 사실까지는 알았는데,

그 다음 노드는 칠한 노드로부터 2*d거리에 있어야 한다. 이런 식으로 접근했던 거 같다.

어차피 리프노드에서 d거리에 있는 노드를 방문하려면 루트에서 해당노드까지는 무조건 방문되어야 하는데, 그걸 눈치채지 못해서 문제를 풀지 못했다.

 

문제

https://www.codetree.ai/missions/9/problems/node-traversal?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N =100001;

int n, s, d, answer;
vector<int> edges[MAX_N];
bool visited[MAX_N]={false, };
int dist[MAX_N]; // dist[i]: 리프노드에서 i번째 노드까지의 거리

void DFS(int x){
    for(int i=0; i<(int)edges[x].size(); ++i){
        int y=edges[x][i];
        if(visited[y]) continue;

        visited[y]=true;
        DFS(y);

        dist[x]=max(dist[x], dist[y]+1);
    }
}
int main() {
    cin >> n >> s >> d;
    for(int i=1; i<n; ++i){
        int a, b;
        cin >> a >> b;
        // 간선 연결
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    
    visited[s]=true;
    DFS(s);

    for(int i=1; i<=n; ++i){
        if(i==s) continue;
        if(dist[i]>=d){
            answer+=2; // 해당 노드를 왔다갔다 해야하니까
        }
    }
    
    cout << answer << '\n';
    return 0;
}