Visiting Cows( BOJ 5934 )

5934. Visiting Cows : https://www.acmicpc.net/problem/5934

5934번: Visiting Cows

 

문제 파악하기

• Bessie에게는 친한 소가 N마리 있으며, N마리의 소 사이에는 트리 형태로 길이 연결되어 있습니다.
• 농부 John은 Bessie에게 이미 만난 소와 인접한 소는 만나선 안 된다고 했습니다.
• 방학을 얻은 Bessie는 N마리의 소를 최대한 많이 만나고 싶어합니다.

 

문제 해결하기

• 문제를 풀기 위해서는 우선 트리 형태로 입력 데이터를 바꿔야 합니다. 이 때, 재귀함수를 사용할 수 있습니다.
• 트리 형태로 바꾼 이후에는 각각의 소(노드)에 대해 2가지 경우의 수를 생각할 수 있습니다.
  1. 현재 노드를 방문하고, 자식 노드를 방문하지 않는 경우
  2. 현재 노드를 방문하지 않고, 자식 노드를 방문하거나 방문하지 않는 경우
• 1번 경우에는 모든 자식 노드가 선택되지 않았을 때, 나올 수 있는 경우를 살펴보면 됩니다.
  2번 경우에는 모든 자식 노드에 대해 나올 수 있는 2가지 경우 중 더 큰 경우를 살펴보면 됩니다.
• 따라서, 현재 노드의 방문 여부에 따른 DP를 적용하면 문제를 해결할 수 있습니다.
  dp[idx][0]: idx번 노드를 방문하지 않은 경우 / dp[idx][1]: idx번 노드를 방문한 경우

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define NMAX 50010
using namespace std;
 
// 입력 변수
int n, a, b;
vector< int > graph[NMAX];
 
// 트리 변수
int check[NMAX];
vector< int > tree[NMAX];
 
// DP 변수
int dp[NMAX][2];
 
void make_tree(int idx) {
    for(int child:graph[idx]) {
        if(check[child]) continue;
 
        check[child] = 1;
        tree[idx].push_back(child);
 
        make_tree(child);
    }
}
 
int sv(int idx, int sw) {
    int ret=0;
 
    if(dp[idx][sw] >= 0) return dp[idx][sw];
 
    // sw: idx번 노드를 방문했는지 여부
    for(int child:tree[idx]) {
        if(sw == 1) ret += sv(child, 0);
        else ret += max(sv(child, 0), sv(child, 1)+1);
    }
 
    return dp[idx][sw] = ret;
 
}
 
int main() {
    // 입력
    scanf("%d", &n);
    for(int i=1;i<n;i++) {
        scanf("%d %d", &a, &b);
 
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    // 트리 만들기
    check[1] = 1;
    make_tree(1);
 
    // DP
    memset(dp, -1, sizeof(dp));
    printf("%d", max(sv(1, 0), sv(1, 1)+1));
 
}