[programmers] 등대

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

tree에서 memoization 기법을 활용한 dp. + dfs?

 

---------------------------------------------------풀이----------------------------------------------------

 

트리 형태로 생각하고 1번 노드를 루트 노드로 잡는다.

dp[light 번호][꺼진경우/켜진경우] = 그 때의 켜진 노드 개수의 최솟값.

즉, 루트 노드에서부터 각 노드가 켜졌을 때와 꺼졌을 때의 켜진 노드의 합의 최솟값을 저장한다.

 

1번 등대를 켜는 경우와 끄는 경우로 나누어 dfs()함수를 두 번 호출하고, 그 중 최소가 답이다.

dfs()함수에서 dp[][]의 값을 계산하는 방식은 다음과 같다.

k번째 depth의 등대가 켜진 경우, 우선 answer에 자신이 켜진 횟수 1을 더해준다.

이 등대와 이웃한 k+1번째 depth의 등대들은 켜져도 되고 꺼져도 되므로 두 경우에서의 최솟값을 찾아 answer에 더해 리턴한다.

k번째 depth의 등대가 꺼진 경우,

이 등대와 이웃한 k+1번째 depth의 등대들은 반드시 켜져야 하므로 answer에 그 값을 더해 리턴한다.

만약 자신이 leaf node인 경우,

켜진 등대이면 1을, 꺼진 등대이면 0을 리턴한다.

#include <string>
#include <vector>
#include <limits.h>
#include <iostream>

using namespace std;

int answer;
int N;
// 1~N까지.
vector<int> map[100'001];
// dp[light 번호][꺼진경우/켜진경우] = 그 때의 켜진 불의 최솟값
int dp[100'001][2] = {0, };
bool visited[100'001] = {false, };

bool is_leaf_node(int n){
    // 다음 방문할 노드가 없으면 leaf node!
    for(int i = 0; i < map[n].size(); i++){
        if(!visited[map[n][i]]){
            return false;
        }
    }
    return true;
}

// 현재 등대 cur, 켤 것인지 나타내는 is_on
int dfs(int cur, bool is_on){
    visited[cur] = true;
    if(is_leaf_node(cur)){
        if(is_on){
            visited[cur] = false;
            return dp[cur][1] = 1;
        }
        else{
            visited[cur] = false;
            return dp[cur][0] = 0;
        }
    }
    
    int answer = 0;
    // 현재 등대의 최솟값을 계산한게 남아있다면 바로 리턴
    if(dp[cur][is_on] > 0){
        visited[cur] = false;
        return dp[cur][is_on];
    }
    
    // 현재 등대가 켜져있다면, 다음 등대가 꺼져있거나 켜져있어야 함
    if(is_on){
        answer += 1;
        for(int i = 0; i < map[cur].size(); i++){
            if(visited[map[cur][i]]){
                continue;
            }
            answer += min(dfs(map[cur][i], false), dfs(map[cur][i], true));
        }
    }
    // 현재 등대가 꺼져있다면, 다음 등대가 켜져있어야 함
    else{
        for(int i = 0; i < map[cur].size(); i++){
            if(visited[map[cur][i]]){
                continue;
            }
            answer += dfs(map[cur][i], true);
        }
    }
    
    visited[cur] = false;
    return dp[cur][is_on] = answer;
}

// 등대 n개, 뱃길 n-1개.
// 뱃길 양쪽 등대 중 적어도 하나는 켜져 있도록 할 때, 켜야하는 최소의 등대 수=?
int solution(int n, vector<vector<int>> lighthouse) {
    answer = 0;
    N = n; 
    for(int i = 0; i < lighthouse.size(); i++){
        map[lighthouse[i][0]].push_back(lighthouse[i][1]);
        map[lighthouse[i][1]].push_back(lighthouse[i][0]);
    }
    // 트리라 생각해서, root인 1번 등대를 켜느냐 마느냐. dp
    answer = min(dfs(1, true), dfs(1, false));
    
    return answer;
}

---------------------------------------------------후기----------------------------------------------------

생각한대로 잘 풀었다! 이번엔 dp를 혼자 힘으로 풀어내서 몹시 뿌듯하다 ㅎㅎ