[백준] 골4 - 트리의 지름

1967번: 트리의 지름

문제 설명

트리에서 임의의 2개의 노드를 선택했을 때, 가장 길이가 긴 값(트리의 지름)을 찾는 문제이다.

풀이

• 임의의 아무 점에서 가장 길이가 긴 노드가 트리의 지름의 첫 번째 노드이고, 그 노드에서 가장 길이가 긴 노드가 트리의 지름의 두 번째 노드이다.

  • 그리디적 사고!

  

  • 이 그림을 보면 알 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> node[10001]; // first: child, second: weight
bool isVisited[10001];
int n;
int farDist = 0;
int dia1 = 1; // diameter first point

void DFS(int p, int len) // param 1: parent, param 2: length
{
	if (isVisited[p])
		return;

	isVisited[p] = true;

	if (len > farDist)
	{
		farDist = len;
		dia1 = p;
	}

	for (int i = 0; i < node[p].size(); i++)
	{
		DFS(node[p][i].first, len + node[p][i].second);
	}
}

int main()
{
	cin >> n;

	int a, b, c;
	for (int i = 0; i < n - 1; i++)
	{
		cin >> a >> b >> c;
		node[a].push_back({ b,c });
		node[b].push_back({ a,c });
	}

	DFS(1, 0);

	farDist = 0;
	memset(isVisited, false, sizeof(isVisited));

	DFS(dia1, 0);

	cout << farDist;
	return 0;
}

소감

• 꿀팁!

  • 트리를 STL로 구현하는 법

  vector<pair<int, int>> node[10001]; // first: child, second: weight
  
  for (int i = 0; i < n - 1; i++)
  	{
  		cin >> a >> b >> c;
  		node[a].push_back({ b,c });
  		node[b].push_back({ a,c });
  	}
  

참조

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