[백준] 15587 Cow at Large (Gold)

정점 N개, 간선 N-1개 트리가 주어지고 루트를 알려준다.

그리고 루트에서 리프노드로 가면 탈출 가능할 때

리프노드에 탈출을 막는 사람을 몇명 둬야하는지 찾는 문제이다.

탈출을 막는 사람과 탈출 하려는 사람의 속도는 같다.

처음에 시도한 방법은

dfs를 돌려서 리프노드에 도착했을 때 루트와 가장 가까운 두갈래 이상의 길을 찾아서 그 정점에 거리를 넣었다.

그리고 마지막에 정점을 다 보며 거리가 들어있으면 루트에서 그 정점까지 거라와 들어있는 거리를 비교해서 수를 세는 것이였는데

바로 망했다 ㅎㅎ 7퍼에서 틀린다. 생각해보니 예외가있따 ㅎㅎ

문제를 푸는 방법을 봤따 ㅎㅎ

푸는 방법은

1. 각 정점에서 루트까지 거리와 가장 가까운 리프까지 거리를 구한다

2. 모든 정점을 돌아보며 

3. 루트가 아니고 && 리프까지 거리 <= 루트까지 거리 && 현재 보는 정점의 부모가 리프까지 거리 > 루트까지 거리 이면 => 답+=1;

4. 문제 더풀어야지 ㅎㅎ

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 100010
vector<int> Graph[MAX_N], d_root(MAX_N), d_leaf(MAX_N);
int n, root,ans;
 
void dist_dfs(int x, int par) {
    d_leaf[x] = (Graph[x].size() == 1) ? 0 : MAX_N;
    if (par == -1) d_root[x] = 0;
    else d_root[x] = d_root[par] + 1;
    for (int next : Graph[x]) {
        if (next != par) {
            dist_dfs(next, x);
            d_leaf[x] = min(d_leaf[x], d_leaf[next] + 1);
        }
    }
}
 
void dfs2(int x, int par) {
    if (par != -1) d_leaf[x] = min(d_leaf[x], d_leaf[par] + 1);
    for (int next : Graph[x]) {
        if (next != par) dfs2(next, x);
    }
}
void go(int x, int par) {
    if (par != -1 && (d_root[x] >= d_leaf[x]) && (d_root[par] < d_leaf[par])) ans += 1;
    for (int next : Graph[x]) {
        if (next != par) go(next, x);
    }
}
int main() {
    scanf(" %d %d", &n, &root);
    root--;
    for (int i = 0; i < n - 1; i++) {
        int x, y; scanf(" %d %d", &x, &y);
        x--; y--;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }
    dist_dfs(root, -1);
    dfs2(root, -1);
    go(root, -1);
    printf("%d\n", (Graph[root].size()==1) ? 1 : ans);
}