14. 등대

https://school.programmers.co.kr/learn/courses/30/lessons/133500

인접한 정점 중 적어도 하나가 색칠되는 문제인데 solve 함수에서 반복되는 실수가 있었다.
자식 노드를 칠하거나 칠하지 않거나 하는 경우의 모든 합을 구해야 하는데 합을 구하지 않고 나오는 경우의 최솟값 하나만 구해서 더하는 실수를 했다.
-> res += tmp, ret += res를 해야 하는데 res = min(res, solve()), ret += res를 했다는 점
이 부분에 대해 좀 더 꼼꼼하게 접근 할 필요가 있다.

#include <bits/stdc++.h>
using namespace std;
const int N = 100002;
vector<int> g[N];
int dp[N][2];

int solve(int x, int p, int c)
{
    // cout << x << ' ' << c << endl;
    int &ret = dp[x][c];
    if (ret != -1) return ret;
    ret = (c == 0) ? 0 : 1;
    int res = 0;
    
    for (int nx : g[x])
    {
        int tmp = 1e9;
        if (nx == p) continue;
        tmp = min(tmp, solve(nx, x, 1));
        if (c == 1)
            tmp = min(tmp, solve(nx, x, 0));
        
        res += tmp;
    }
    
    ret += res;
    return ret;
}

int solution(int n, vector<vector<int>> tmp) 
{

    memset(dp, -1, sizeof dp);
    for (auto to : tmp)
    {
        int u = to[0], v = to[1];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    int r1 = solve(1, 0, 0);
    int r2 = solve(1, 0, 1);
    // cout << r1 << ' ' << r2 << endl;
    return min(solve(1, 0, 0), solve(1, 0, 1));
}```