[프로그래머스]연습>>등대

문제 설명

인천 앞바다에는 1부터 n까지 서로 다른 번호가 매겨진 등대 n개가 존재합니다. 등대와 등대 사이를 오가는 뱃길이 n-1개 존재하여, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있습니다. 등대 관리자 윤성이는 전력을 아끼기 위하여, 이 중 몇 개의 등대만 켜 두려고 합니다. 하지만 등대를 아무렇게나 꺼버리면, 뱃길을 오가는 배들이 위험할 수 있습니다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.

예를 들어, 아래 그림과 같이 등대 8개와 7개의 뱃길들이 있다고 합시다. 이 경우 1번 등대와 5번 등대 두 개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있으므로, 배들은 안전하게 운항할 수 있습니다.

등대의 개수 n과 각 뱃길이 연결된 등대의 번호를 담은 이차원 배열 lighthouse가 매개변수로 주어집니다. 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

트리에서 dp문제입니다.

dp배열을 2차원으로 생성합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

vi adj[100001],ch[100001];
int dp[100001][2];
int v[100001];
void dfs(int n){
    v[n]=1;
    if(adj[n].size()==1 && n!=1){
        //리프노드
        dp[n][1]=1;
        return;
    }
    for(int r:adj[n]){
        if(!v[r]){
            ch[n].push_back(r);
            dfs(r);
        }
    }
    dp[n][1]++;
    for(int r:ch[n]){
        dp[n][1]+=min(dp[r][0],dp[r][1]);
        dp[n][0]+=dp[r][1];
    }
}
int solution(int n, vector<vector<int>> lighthouse) {
    for(vi a:lighthouse){
        adj[a[0]].push_back(a[1]);
        adj[a[1]].push_back(a[0]);
    }
    dfs(1);
    return min(dp[1][0],dp[1][1]);
}