BOJ 15587 Cow at Large (Gold)

https://www.acmicpc.net/problem/15587

15587번: Cow at Large (Gold)

 

1차 접근

Bassie 기준 Depth와, Farmers  기준 Depth 둘 다 구해놓고, 어떻게 계산하면 잘 되지 않을 까 생각했었다. 하지만, Depth 값 만으로는 여러 예외 case 를 처리할 수 없었기 때문에 생각하는 것을 그만 두었다.

2차 접근

Bassie 기준 Depth 를 구해 놓고, Farmer 들을 BFS로 움직여보자라고 생각했다.
하지만 이 또한 BFS 에서 시작점이 여러개라는 조건 하나 때문에 많은 예외가 나오는 바람에  좀 더 단순화 하려고 했다. 

3차 접근

그렇다면 거꾸로 Farmer 의 Depth를 먼저 구해놓고, Bassie를 움직이면 어떨 까 생각했다. 움직이는 주체가 하나이기 때문에, 좀더 고려가 쉬워졌다. 탐색을 BFS 에서 DFS 로 바꾸면 탐색경로에서 Farmer 를 만날 때 마다 count 를 1씩 증가시켜주면 되었다.

코드는 다음과 같다.

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int n, k, a, b, answer;
vector<vector<int>> graph;
vector<int> leaf;

int depth_bessie[100001];
int depth_law[100001];

void dfs(int now, int depth){
    
    if(depth_bessie[now] <= depth) return;
    depth_bessie[now] = depth;
    if(depth_bessie[now] >= depth_law[now]){
        //printf("now : %d\n",now);
        answer += 1;
        return;
    }
    for(int next : graph[now]){
        dfs(next,depth + 1);
    }
}

int main(){
    
    scanf("%d%d",&n,&k);
    graph.resize(n+1);
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    queue<int> q;
    for(int i=1;i<=n;i++) {
        depth_bessie[i] = depth_law[i] =  0xfffffff;
        if(graph[i].size() == 1){
            depth_law[i] = 0;
            q.push(i);
        }
    }

    while(q.size()){
        int now = q.front();
        q.pop();
        for(auto next : graph[now]){
            if(depth_law[next] == 0xfffffff){
                depth_law[next] = depth_law[now] + 1;
                q.push(next);
            }
        }
    }

    dfs(k,0);
    printf("%d\n",answer);
    

    return 0;
}