programmers Level 3 모두 0으로 만들기

문제

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

걸린 시간

- 실패

풀이

C++

#include <iostream>
#include <string>
#include <vector>
typedef long long ll;

using namespace std;

ll ans = 0;
vector<int> visited;
vector<vector<int>> adj;

ll solve(int c, vector<ll>& a){
    for(int i = 0; i < adj[c].size(); i++){
        int n = adj[c][i];
        if(!visited[n]){
            visited[n] = 1;
            ll m = solve(n, a);   
            a[c] += m;
            ans += abs(m);
        }
    }
    return a[c];
}

ll solution(vector<int> a, vector<vector<int>> edges) {
    vector<ll> A;
    for(int x : a) A.push_back(x);
    int n = a.size();
    adj.resize(n);
    for(int i = 0; i < edges.size(); i++){
        int u = edges[i][0];
        int v = edges[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    visited.resize(n, 0);
    visited[0] = 1;
    if(solve(0, A)) return -1;
    else return ans;
}

"모든 트리가 가중치를 0으로 만들 수 있는것은 아닙니다." 라는 문장에서 '모든'이 주어진 트리에서 나올 수 있는 다른 트리 형태를 뜻하는 것인 줄 알았다. (트리는 한 정점을 골라 들어 올렸을 때 또 다른 트리 형태가 만들어진다.) 펜과 종이가 없어 다양한 예제를 손으로 풀어보지 못했기에 트리의 순서가 크게 영향을 미치는 줄로만 알았다. 뒤늦게 트리의 어느 정점을 선택해도 같은 결과가 나온다는 걸 알아차렸고 0번 정점을 루트로 하여 dfs 를 시도했지만 일부 케이스에서 틀렸습니다가 출력되었다. 대회가 끝나고 보니 정점의 가중치를 관리하는 배열 a 의 자료형이 int 였다.

문제의 해석도 세심한 구현도 부족했던 문제.