[프로그래머스] 76503 모두 0으로 만들기 (C/C++)

문제

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

풀이

문제를 읽고, 우선 이 그래프가 특별히 트리 구조임을 인지했다. Edge의 개수가 Node의 개수보다 1 작다는 점을 통해 다시 확인할 수 있었다. 따라서 주어진 구조는 사이클이 없고 모든 노드가 최소한의 간선으로 연결되어 있음을 알 수 있었다. 트리 구조의 특성상 어떤 노드를 루트로 잡아도 되기에, 0번 노드를 루트로 잡고 DFS를 수행했다. 트리의 특성을 잘 활용하면 비교적 어렵지 않게 해결할 수 있는 문제였다.

코드를 제출하고 일부 테스트케이스에서 실패하여 어디서 문제가 발생했는지 1시간 정도 고민했다. 문제는 인자로 받은 std::vector<int> a를 그대로 사용해서, 값들을 누적하면서 계산하는 과정에서 int의 범위를 초과하는 경우가 발생했기 때문이었다. 자료형 오버플로우를 염두에 두고 있었음에도 불구하고 이를 놓쳤다는 점이 아쉬웠다. 주어진 인자를 그대로 사용하지 않고 타입을 바꿔줘야하는 경우가 있으리라고는 상상도 못했고, 다음에 같은 일이 있어도 눈치채기 어려울 것 같다.

소스 코드

C++17

#include <bits/stdc++.h>

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

    for (const auto &edge: edges) {
        ret[edge[0]].push_back(edge[1]);
        ret[edge[1]].push_back(edge[0]);
    }

    return ret;
}

long long solution(std::vector<int> a, std::vector<std::vector<int>> edges) {
    const size_t N = a.size();
    const auto &graph = build_graph(N, edges);
    std::vector<long long> lla(a.begin(), a.end());

    std::function<long long(const size_t, const size_t)>
    dfs = [&] (const size_t current, const size_t parent) {
        long long ret = 0;

        for (const int next: graph[current]) {
            if (next == parent) {
                continue;
            }
            ret += dfs(next, current);
        }

        if (parent == N) {
            return lla[current] == 0 ? ret : -1;
        }

        ret += std::abs(lla[current]);
        lla[parent] += lla[current];
        lla[current] = 0;

        return ret;
    };

    return dfs(0, N);
}

[프로그래머스] 76503 모두 0으로 만들기 (C/C++)

문제

풀이

소스 코드

Share this post