[백준/C++] 1967 트리의 지름 (G4)

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

<내 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int n, p, c, cost;
vector<pair<int, int>> tree[10001];
int maxi = -1;
int each[10001];

int Recursion(int root)
{
	if(each[root]>-1)
		return each[root];
	if(tree[root].size() == 0)
		return each[root] = 0;
	
	int longest = 0, sub = 0;
	vector<int> cand;
	for(int i=0; i<tree[root].size(); i++)
	{
		sub = Recursion(tree[root][i].first) + tree[root][i].second;
		if(longest < sub)
			longest = sub;
	}
	return each[root] = longest;
}



int main(void)
{
	cin >> n;
	
	for(int i=1; i<n; i++)
	{
		cin >> p >> c >> cost;
		tree[p].push_back({c, cost});
		each[i] = -1;
	}each[n] = -1;
	
	int sum;
	vector<int> cand;
	
	for(int i=1; i<=n; i++)
	{
		cand.clear();
		sum = 0;

		for(int j=0; j<tree[i].size(); j++)
			cand.push_back(Recursion(tree[i][j].first) + tree[i][j].second); 
		
		sort(cand.begin(), cand.end());
		if(cand.size() > 1)
			sum = cand[cand.size()-1] + cand[cand.size()-2];		
		else if(cand.size()==1)
			sum = cand[0];
		
		if(sum > maxi)
			maxi = sum;
	}

	cout << maxi;
}

 

 종만북에서 비슷한 문제(요새)를 풀어봤는데, 트리에서 가장 긴 경로를 찾는게 유명한 문제인 것 같다. 트리의 지름은 곧 트리 안에서 가장 멀리 떨어진 두 노드를 가리킨다. 이때 ‘멀리 떨어졌다’는 것은 가중치가 있는 경우에는 가중치가 가장 큰 경우, 그렇지 않으면 간선을 몇 개 거치느냐로 구분할 수 있겠다.

 

 나는 기본적으로 재귀적이라는 트리의 특성을 이용해 DFS로 특정 노드의 서브트리 노드들 중 가장 큰 비용으로 도달해야 하는 경우의 비용을 return하는 재귀함수를 만들었다. 그리고 main함수에서는 for문으로 모든 노드에 대해 Recursion(node)를 실행하고, 그 결과를 vector들에 모은 후 가장 큰 두 값을 더해서 이때까지의 최대값과 비교한다.

가중치의 합이 가장 큰 두 쌍은 언제나 잎-잎 노드 쌍일 것이기에 모든 잎 노드 쌍을 방문해보는 코드를 작성해야 하고, 잎-잎 노드 쌍은 반드시 그 둘의 공통된 root를 지난다.

따라서 모든 노드에 대해 그것들을 root로 하여 자식 노드 중 가장 큰 cost로 도달할 수 있는 노드 두 쌍을 선정해 둘을 더한다 ⇒ 이게 곧 경우의 수 한 가지를 시도한 것이다. 모든 노드에 대해 이 과정을 반복하므로 모든 쌍을 검사할 수 있고 그 중 가장 큰 값을 고르면 된다.

 

 

<다른 코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int cnt;
vector<pair<int, int>> v[10002];

int findMax(int node) {
	//가장 큰 가중치를 담을 temp1 변수
    int temp1 = 0;
    //두번째로 큰 가중치를 담을 temp2 변수
	int temp2 = 0;
	
	for (int i = 0; i < v[node].size(); i++) {
    	//각 간선의 최대 가중치+ 연결되어있는 가중치
		int cal = findMax(v[node][i].first) + v[node][i].second;
		if (temp1 < cal) {
        	//간선의 가중치 최대값을 초기화 해 주고,
			temp2 = temp1;
			temp1 = cal;
		}
		else if (temp2 < cal) {
        	//만약 cal이 가장 크지 않지만, 2번째로 클 수도 있기에,
			temp2 = cal;
		}
	}
	if (cnt < temp1 + temp2) {
    	//각 부분 노드들의 각각 가중치를 더했을 때와 비교
		cnt = temp1 + temp2;
	}
    //한 간선만 리턴을 해 줘야 함.
	return temp1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int str, dest, cost;
		cin >> str >> dest >> cost;
		v[str].push_back({ dest,cost });
	}

	findMax(1);

	cout << cnt << "\n";
}

//https://tackdoo.tistory.com/10

다른 사람들의 코드를 보니 내가 수행한 main함수에서의 과정, 재귀함수의 작동을 하나로 합쳐서 재귀함수로 구현했다. 

나는 일단 루트 노드가 1로 고정이라는 것을 생각하지 못보고 코드를 짜서 반복문 안에 함수 호출을 집어 넣었는데, 이 문제에서는 위 코드처럼 1을 매개변수로 전달하는 함수의 호출 한 번으로 문제 해결이 가능하다.

 

결국 재귀함수가 하는 일은 특정 노드에서 가장 멀리 있는 노드까지의 거리를 반환하는 것이고, 필요한 값은 (가장 멀리 있는 노드까지의 거리 + 둘 째로 멀리 있는 노드까지의 거리) 중 가장 큰 값이므로 가장 멀리 있는 노드까지의 거리를 구해서 그 값을 넘기면서 재귀호출하되, 구하려는 최대 값의 갱신도 해주면 문제에 필요한 모든 값을 구할 수 있다.