[1일 1알고] 등대

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

프로그래머스

1일 1알고리즘이라고 해놓고 빼놓는 날이 생기네요

다시 힘내보겠습니다

 

연관된 간선을 모두 활성화하는 가장 적은 노드의 수를 골라야합니다.

 

처음에는 문제를 잘못이해해서 간선이 아니라 노드를 활성화해야한다고 착각해서 오래걸렸네요.

 

예를 들어 1-2-3-4-5-6 과 같이 연결되어있다면 최소 값이 2가 아니라 문제에서는 3이라는 의미입니다.

---

문제는 Tree DP를 이용하는 문제입니다.

Tree DP의 경우 leaf node부터 시작해 결과를 끌어모으는 형태의 dp입니다.

 

dp의 상태는 다음과 같습니다. 

1. 내가 활성화하지 않았다 = 자식이 활성화했다.

2. 내가 활성화한다.

 

반드시 자식과 본인 둘 중 하나이상이 활성화되어야 간선이 활성화될 수 있습니다. 

 

이를 DFS로 나타내면 아래와 같습니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> graph;
vector<vector<int>> dp;

void dfs(int u, int parent)
{
    dp[u][0] = 0; 
    dp[u][1] = 1; 

    for (int v : graph[u])
    {
        if (v == parent)
            continue;

        dfs(v, u);

        dp[u][0] += dp[v][1];

        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

int solution(int n, vector<vector<int>> lighthouse)
{
    graph.assign(n + 1, vector<int>());
    dp.assign(n + 1, vector<int>(2, 0));

    for (auto& edge : lighthouse)
    {
        int a = edge[0];
        int b = edge[1];

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1, 0);

    return min(dp[1][0], dp[1][1]);
}

현재 위치 u에서 간선과 연결된 자식노드 v의 상태를 번갈아가며 확인합니다.

 

---

이렇게만 보면 해당 문제는 해결이지만 아쉽게도 저는 노드를 활성화해야한다고 착각해 문제가 복잡해졌습니다.

이에 대한 내용도 첨부합니다.

 

void dfs(int u, int parent)
{
    dp[u][0] = 1;
    dp[u][1] = 0;
    dp[u][2] = 0;

    bool hasChild = false;
    int extraCost = INF;

    for (int v : graph[u])
    {
        if (v == parent)
            continue;

        hasChild = true;

        dfs(v, u);

        dp[u][0] += min({ dp[v][0], dp[v][1], dp[v][2] });

        dp[u][2] += min(dp[v][0], dp[v][1]);

        int best = min(dp[v][0], dp[v][1]);
        dp[u][1] += best;

        extraCost = min(extraCost, dp[v][0] - best);
    }

    if (!hasChild)
    {
        dp[u][1] = INF;
    }
    else
    {
        dp[u][1] += extraCost;
    }
}


int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;

    graph.resize(n + 1);
    dp.resize(n + 1);
    for (auto light : lighthouse)
    {
        graph[light[0]].push_back(light[1]);
        graph[light[1]].push_back(light[0]);
    }
    dfs(1, 0);

    answer = min(dp[1][0], dp[1][1]);
    return answer;
}

이 경우에는 하나의 노드에 대해서 활성화될 수 있는 방법은 본인이 활성화하거나, 본인의 부모가 활성화하거나, 본인의 자식이 활성화하는 방법으로 나뉘어져있습니다.

 

만약 내가 활성화한다면 자식의 상태는 상관없습니다. 

만약 부모의 활성화를 원한다면 자식의 상태는 딱히 상관없습니다.

만약 자식의 활성화를 원한다면 자식 중 단 하나만 활성화했으면 됩니다.

 

이 경우를 계산합니다.

 

여기서 문제는 모든 자식의 상태를 v[1] = 활성화되지 않은 상황으로 보았을 때입니다.

하나라도 활성화되어야하기 때문에 자식이 가질 수 있는 전환비용([v][0] -> [v][1]) 중 최솟값을 [u][1] (자식의 활성화를 바람) 에 추가합니다.

 

어우 어렵네요