[프로그래머스] 133500 등대 (C/C++)

문제

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

풀이

트리 구조에서 최소값을 구하는 문제이다. 상태는 현재 노드가 켜져있는지 꺼져있는지로 총 두 가지이다. 상태가 많지 않아 동적 계획법을 활용해 해결했다. 기본적인 그래프 탐색 로직을 DFS로 구현하여 풀었다. 같은 로직을 활용하여 푼 [프로그래머스] 76503 모두 0으로 만들기 (C/C++) 문제와 매우 유사하다.

소스 코드

C++17

#include <bits/stdc++.h>

typedef enum e_state {
    OFF = 0,
    ON = 1,
}   t_state;

std::vector<std::vector<size_t>> build_graph(const size_t n, const std::vector<std::vector<int>> &lighthouses) {
    std::vector<std::vector<size_t>> ret(n);

    for (const auto &lighthouse: lighthouses) {
        ret[lighthouse[0] - 1].push_back(lighthouse[1] - 1);
        ret[lighthouse[1] - 1].push_back(lighthouse[0] - 1);
    }

    return ret;
}

int solution(int n, std::vector<std::vector<int>> lighthouses) {
    const auto &graph = build_graph(n, lighthouses);
    std::vector<std::array<int, 2>> dp(n, { INT_MAX, INT_MAX });

    std::function<int(const size_t, const size_t, const bool)>
    dfs = [&] (const size_t current, const size_t parent, const bool state) {
        if (dp[current][state] != INT_MAX) {
            return dp[current][state];
        }

        dp[current][state] = state;

        for (const size_t next: graph[current]) {
            if (next != parent) {
                if (state == OFF) {
                    dp[current][state] += dfs(next, current, ON);
                } else {
                    dp[current][state] += std::min(dfs(next, current, ON), dfs(next, current, OFF));
                }
            }
        }

        return dp[current][state];
    };

    return std::min(dfs(0, n, OFF), dfs(0, n, ON));
}

[프로그래머스] 133500 등대 (C/C++)

문제

풀이

소스 코드

Share this post