백준 1167번: 트리의 지름 (C++)

 

문제 링크 : www.acmicpc.net/problem/1167

 

 

 

tip) 임의의 한 점에서 제일 먼 점은 반드시 지름의 양 끝 점 중에 하나라는 사실만 생각해내면 된다.

 

 

<전체적인 알고리즘>

1. 임의의 한 점에서 제일 먼 점을 찾는다. (지름의 끝 점 중 하나를 찾는다)

2. 그 점으로 부터 제일 먼 점까지의 거리를 구한다 

 

   -> 제일 먼 점을 찾는건 bfs 나 dfs로 구한다.

 

 

 

 

<전체 코드>

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

using namespace std;

vector<pair<int, int>> a[100002];
bool check[100002];
int max_cost = 0;
int result = 0;

int find_corner(int start)
{
	queue<pair<int, int>> q;
	q.push(make_pair(start, 0));
	check[start] = true;
	max_cost = 0;
	int corner = 0;

	while (!q.empty())
	{
		int node = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (max_cost < cost)
		{
			corner = node;
			max_cost = cost;
		}

		for (int i = 0; i < a[node].size(); i++)
		{
			int next = a[node][i].first;
			int edge = a[node][i].second;
			if (check[next])continue;
			check[next] = true;
			q.push(make_pair(next,cost+edge));
		}
	}
	return corner;
}


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

	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++ )
	{
		int n1;
		cin >> n1;
		while (1)
		{
			int n2, edge;
			cin >> n2;
			if (n2 == -1)break;
			cin >> edge;
			a[n1].push_back(make_pair(n2, edge));
			a[n2].push_back(make_pair(n1, edge));
		}
	}

	int corner= find_corner(1);   //제일 구석탱이 node 찾기 (지름의 끝점 중 한 점)
	fill(&check[0], &check[100001], 0);
	find_corner(corner);   //나머지 끝점까지의 거리 구하기
	cout << max_cost;
	return 0;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.