프로그래머스 Level 3 0으로만들기

0으로만들기 (프로그래머스 Level 3)

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

어렴풋이 dfs로 풀 수 있겠다 생각은 하였으나
(tree 구조로 주어지기에)
구체적인 구현으로 들어가자 자꾸 다른 값이 나왔기에
결국 힌트를 보았다
(https://ansohxxn.github.io/programmers/136/);

요점은 ‘부모’ 노드에게 ‘자신’의 값을 주는 방식으로
DFS를 돌리는 것이였다
결과적으로는 ‘리프’노드에서 ‘루트’노드로 값을 주는 방식으로 계산할 수 있었다
(특정한 부분에 합을 부모까지 끌고온다는 점에서 ‘누적합’에 대한 개념이 포함될지도)

Code

#include <vector>
#include<unordered_map>
#include<math.h>

using namespace std;

void dfs(unordered_map<int, vector<int>>& m, const vector<int>& a, vector<long long>& sum, int start,int parent, vector<bool>& visited,long long& answer)
{
	visited[start] = true;

	for (int road : m[start])
	{
		if (visited[road])
			continue;

		dfs(m, a, sum, road,start,visited, answer);
	}

	sum[parent] += sum[start];
	answer += abs(sum[start]);
}

long long solution(vector<int> a, vector<vector<int>> edges) {
	unordered_map<int, vector<int>> m;
	for (const auto& edge : edges)
	{
		int s = edge[0];
		int t = edge[1];
		if (s > t)
			swap(s, t);

		if (m.find(s) == m.end())
			m[s] = vector<int>();
		m[s].push_back(t);
		if (m.find(t) == m.end())
			m[t] = vector<int>();
		m[t].push_back(s);
	}

	vector<long long> sum(a.size(),0);
	for (int i = 0; i < a.size(); i++)
		sum[i] = a[i];

	long long answer = 0;
	vector<bool> visited(a.size(), false);

	dfs(m, a, sum, 0, 0,visited, answer);

	if (sum[0] != 0)
		return -1;

	return answer;
}