백준, boj) 1967. 트리의 지름 ( C / C++)

1. 문제 링크

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

1967번: 트리의 지름

2. 문제 개요

 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 트리의 지름을 구해서 출력하는 프로그램을 작성하시오.

 

3. 문제 힌트

루트에서 가장 먼 노드를 찾아가서 거기서 가장 먼 노드를 찾기.

 

4. 문제 풀이

우선 인접리스트를 만들어야 한다. 그리고 양방향 간선을 연결해주자.

 

root에서 가장 먼 노드를 BFS로 찾는다. 그리고 그 점을 시작으로 가장 먼 노드를 찾으면 그것이 트리의 지름이 된다.

 

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
//left, weight
vector<pair<int,int>>adj[10001];
queue<pair<int,int>> q;
bool visited[10001];
 
int main()
{
	int n;
	scanf("%d", &n);
 
	for (int i = 0; i < n-1; ++i){
		int cur, child, weight;
 
		scanf("%d %d %d", &cur, &child, &weight);
 
		adj[cur].push_back(make_pair(child, weight));
		adj[child].push_back(make_pair(cur, weight));
	}
 
	//루트로 부터 가장 먼 노드 찾기.
	fill(visited, visited + 10001, false);
	q.push({ 1,0 });
	visited[1] = true;
	int ansv = -1;
	int answ = -1;
	while (!q.empty())
	{
		int cv = q.front().first; 
		int cw = q.front().second;
		q.pop();
 
		if (answ < cw) {
			answ = cw;
			ansv = cv;
		}
		int len = adj[cv].size();
 
		for (int i = 0; i < len; ++i)
		{
			int nv = adj[cv][i].first;
			int nw = cw + adj[cv][i].second;
 
			if (!visited[nv])
			{
				visited[nv] = true;
				q.push({ nv,nw });
			}
		}
	}
	
	//루트로부터 가장 먼 노드로 부터 시작해서 가장 먼 노드 찾기
	//그냥 BFS한번 더
 
	fill(visited, visited + 10001, false);
	q.push({ ansv,0 });
	answ = 0;
	visited[ansv] = true;
	
	while (!q.empty())
	{
		int cv = q.front().first;
		int cw = q.front().second;
		q.pop();
 
		if (answ < cw) {
			answ = cw;
			ansv = cv;
		}
		int len = adj[cv].size();
 
		for (int i = 0; i < len; ++i)
		{
			int nv = adj[cv][i].first;
			int nw = cw + adj[cv][i].second;
 
			if (!visited[nv])
			{
				visited[nv] = true;
				q.push({ nv,nw });
			}
		}
	}
 
 
 
 
	printf("%d", answ);
 
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~