[Programmers] 모두 0으로 만들기

안녕하세요. 이번 포스팅에서는 프로그래머스 모두 0으로 만들기라는 문제를 풀어보도록 하겠습니다.

 

해당 문제는 

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

코딩테스트 연습 - 모두 0으로 만들기

 

위 링크에서 확인하실 수 있습니다.

 

 

이 문제를 해결하는데, 중요한 키는 트리 구조라는 것입니다.

 

root를 아무 노드나 설정하셔서, 트리를 탐색하시면서 문제의 요구사항을 구현하는 것이 중요합니다.

 

 

예시를 자세히 보시면, 결국 루트로부터 리프 노드까지 탐색을 진행한 뒤, 리프 노드부터 0으로 만들어주시면 됩니다.

 

이때 리프 노드의 부모 노드는 리프 노드의 저장된 값을 0으로 만들기 위해 switching을 절댓값(리프 노드의 값)만큼 수행해주어야 합니다.

 

결과적으로 #3번 노드의 경우 #2번 노드와 #4번 노드가 각각 2/2를 가지고 있기 때문에 각각 2번씩 수행한 뒤, #3에 저장된 값에 +4를 해주시면 됩니다.

 

그다음 같은 작업을 #3번과 #5번에 대해서 수행해주시고, 이러한 방식으로 루트노드까지 도달할 경우에 필요한 수행 개수를 반환해주시면 됩니다.

 

* 처음에 a배열을 한번 순회하며, 모두 0인지 혹은 a배열에 있는 값들을 모두 더한 값이 0이 아닌지 확인해주셔야 합니다. 애초에 합이 0이 되지 않으면, 아무리 수행을 하더라도 모두 0으로 만들 수 없습니다.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
bool visited[300004];
vector<ll> e[300004];
ll ans = 0;
void go(ll cur, vector<ll>& a) {
    for(int i = 0; i < e[cur].size(); i++) {
        ll next = e[cur][i];
        if(visited[next]) continue;
        visited[next] = 1;
        go(next, a);
        
        a[cur] += a[next];
        ans += abs(a[next]);
    }
}
long long solution(vector<int> a, vector<vector<int>> edges) {
    long long answer = 0;
    
    vector<ll> aCopy;
    int zCount = 0, sum = 0;
    for(int i = 0; i < a.size(); i++) {
        if(a[i] == 0) zCount++;
        sum += a[i];
        aCopy.push_back((ll)a[i]);
    }
    
    if(zCount == a.size()) return 0;
    if(sum != 0) return -1;
    
    for(int i = 0; i < edges.size(); i++) {
        e[edges[i][0]].push_back(edges[i][1]);
        e[edges[i][1]].push_back(edges[i][0]);
    }
    
    visited[0] = 1;
    go(0, aCopy);

    return ans;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.