[Programmers] 모두 0으로 만들기

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/76503

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

주어진 자료형은 int지만 더하는 과정에서 오버플로우가 발생할 수 있으므로 long long으로 변환해야 하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 가중치의 합산이 0이 아니라면 가중치를 모두 0으로 만드는 것이 불가능합니다.

1.1 따라서 0이 아닐 경우 -1을 반환해줍니다.

2. 트리는 모든 노드가 연결되어있으므로 어느 노드를 루트로 잡아도 상관이 없습니다. 따라서 간단하게 0을 루트로 해서 DFS를 돌립니다.

2.1 DFS를 돌리면서 각 가중치를 업데이트 합니다. (결국 두 노드의 가중치를 합산한 값이 업데이트하는 최소 횟수)

3. 2번에서 구한 가중치의 합산을 반환해줍니다.

 

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <queue>
	#include <cmath>
	using namespace std;
	const int MAX = 300000 + 300;
	long long result;
	bool visited[MAX];
	vector<long long> weights;
	vector<int> connected[MAX];
	long long func(int node)
	{
	visited[node] = true;
	for (int next : connected[node])
	{
	if (visited[next])
	{
	continue;
	}
	weights[node] += func(next);
	}
	result += abs(weights[node]);
	return weights[node];
	}
	long long solution(vector<int> a, vector<vector<int>> edges) {
	long long sum = 0;
	for (int num : a)
	{
	sum += num;
	weights.push_back(num);
	}
	if (sum)
	{
	return -1;
	}
	for (auto edge : edges)
	{
	connected[edge[0]].push_back(edge[1]);
	connected[edge[1]].push_back(edge[0]);
	}
	func(0);
	return result;
	}
	int main(void)
	{
	vector<int> a = { -5, 0, 2, 1, 2 };
	vector<vector<int>> edges = {
	{0, 1},
	{3, 4},
	{2, 3},
	{0, 3}
	};
	cout << solution(a, edges) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~