[백준] 1967번: 트리의 지름(C++)

문제 링크

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

 

 

코드 구현

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

using namespace std;

vector<vector<pair<int, int>>> tree;
vector<bool> visited;
int maxDist = 0, farNode = 0;

void dfs(int node, int dist)
{
	visited[node] = true;

	if (dist >= maxDist)
	{
		maxDist = dist;
		farNode = node;
	}

	for (const pair<int, int> pair : tree[node])
	{
		int neighbor = pair.first;
		int weight = pair.second;

		if (!visited[neighbor])
		{
			dfs(neighbor, dist + weight);
		}
	}
}

int main()
{
	int n;
	cin >> n;

	tree.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 0; i < n - 1; i++)
	{
		int p, c, w;
		cin >> p >> c >> w;
		tree[p].push_back(make_pair(c, w));
		tree[c].push_back(make_pair(p, w));
	}

	// dfs로 가장 먼 노드 구하기
	dfs(1, 0);

	// 이 노드에서 가장 먼 노드의 거리 구하기
	// visited, maxDist 초기화
	fill(visited.begin(), visited.end(), false);
	maxDist = 0;
	dfs(farNode, 0);

	cout << maxDist << endl;

	return 0;
}

 

 

해결 방법

• 임의의 노드에서 가장 먼 노드 찾기
• 그 노드에서 다시 가장 먼 노드 찾기
• 두 노드 사이의 거리가 트리의 지름

위 방법을 참고하여 dfs를 이용해 시작 노드(1번)에서 가장 먼 노드를 찾고, 그 노드에서 다시 dfs를 돌아 가장 먼 노드를 찾았다.

처음에는 가중치를 따로 저장하는 벡터를 만들어서 시도해 봤는데 그렇게 되면 부모->자식으로 내려갈 때는 문제가 없지만, dfs의 시작 노드가 루트 노드가 아닌 특정 노드로 시작하게 된다면 자식 -> 부모로 접근할 때 부모에 있는 가중치가 합해지는 문제가 생겨 pair<int, int>를 사용해 tree를 노드 정보를 구현하였다.