BOJ 백준 1289 : 트리의 가중치

시작하면서

　이번 문제는 트리(Tree) 의 속성과 관련된 문제이다.

BOJ 1289 - 트리의 가중치

​

문제 이해

​ 이 문제에서는 용어 2개를 정의한다.

1. 경로의 가중치 : 경로에 해당하는 간선의 곱
2. 트리의 가중치 : 트리 상에 가능한 모든 경로에 대해 경로의 가중치의 합

​ 이 문제의 최대 트리 정점 개수가 100,000개이므로, 단순히 전부 계산하는 O(N^2)의 방식으로 문제를 풀려고 접근하면 시간 초과가 발생한다. 트리의 특성상 사이클이 존재하지 않으므로 한 번에 전부 순회하는 방식으로 O(N)의 시간 복잡도로 문제를 풀어야함을 예상해 볼 수 있다.

​ 그런데 여기까지만 생각하고 문제를 풀지 못했다. 구글링을 통해 검색한 결과 공식을 만들어냈어야 했는데 해당 부분에 대한 접근이 부족했다. 참고한 블로그 링크를 남긴다.

블로그

​

해결

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define DIVIDE_NUMBER (1000000007)

class info
{
public:
	int previousNode;
	int currentNode;
	int routeWeight;
};

long long FindPath(const vector<vector<pair<int, int>>>& graph, long long &result, int currentNode, int previousNode)
{
	long long multiply = 1;

	for (int i = 0; i < graph[currentNode].size(); i++)
	{
		int nextNode = graph[currentNode][i].first;
		int weight = graph[currentNode][i].second;

		if (nextNode == previousNode)
		{
			continue;
		}

		long long subTreeResult = FindPath(graph, result, nextNode, currentNode) * weight % DIVIDE_NUMBER;
		result += (subTreeResult * multiply) % DIVIDE_NUMBER;
		result %= DIVIDE_NUMBER;
		multiply = (multiply + subTreeResult) % DIVIDE_NUMBER;
	}

	return multiply;
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<vector<pair<int, int>>> graph;
	int N;

	cin >> N;

	graph.resize(N + 1);
	for (int i = 0; i < N - 1; i++)
	{
		int A, B, W;
		cin >> A >> B >> W;

		graph[A].push_back(make_pair(B, W));
		graph[B].push_back(make_pair(A, W));
	}

	long long result = 0;
	FindPath(graph, result, 1, 0);

	cout << result % DIVIDE_NUMBER;

	return 0;
}