[BOJ]1167번 : 트리의 지름 (c++)

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

1167번: 트리의 지름

 

 

dfs 탐색을 2번하기. 첫번째 탐색에서 구한 말단노드를 두번째 탐색의 시작점으로.

#include <iostream>
#include <vector>

using namespace std;

struct node {
	int to, weight;
};

int max_cost;
int end_node;

void dfs(vector<vector<node>> &tree, vector<bool> &visit, int now, int cost)
{
	visit[now] = true;
	
	// 최대값과 최대값 시점 말단 노드 갱신
	if (max_cost < cost)
	{
		max_cost = cost;
		end_node = now;
	}

	// 자식 노드 탐색
	for (node c : tree[now])
	{
		// 방문하지 않은 자식노드면 비용을 더하고 dfs 재귀함수 호출
		if (!visit[c.to])
		{
			dfs(tree, visit, c.to, cost + c.weight);
		}
	}
}

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

	// 입력받아 가중치 있는 인접리스트 만들기
	int V;
	cin >> V;
	vector<vector<node>> tree(V + 1, vector<node>());
	for (int i = 1; i <= V; ++i)
	{
		int from, to, weight;
		cin >> from;
		while (true)
		{
			cin >> to;
			if (to == -1)
			{
				break;
			}
			cin >> weight;

			tree[from].push_back({ to, weight});
		}
	}

	/*
		임의 노드에서부터 깊이우선탐색으로 
		최대 비용과 비용을 최대로 하는 말단 노드 구하기
		(어디에서부터 시작해도 해당 노드로부터 최대비용을 만드는 말단 노드가 구해진다)
	*/
	vector<bool> visit(V + 1);
	dfs(tree, visit, 1, 0);
	
	/*
		첫번째 탐색에서 구한 말단 노드부터 깊이우선탐색 시작
		최대 비용과 비용을 최대로 하는 말단 노드 구하기
	*/
	fill(visit.begin(), visit.end(), 0);
	dfs(tree, visit, end_node, 0);

	// 출력
	cout << max_cost;

	return 0;
}

 

 

dfs탐색을 2번 하는 것이 포인트!!!

bfs로도 가능하지만, 최대의 가중치값을 구하는 것이므로

dfs가 적합하다고 판단했다.

 

 

아래 그림과 같은 트리가 있다고 하자.

노드는 6개이고, 간선에는 가중치가 있다.

6번 노드가 없는 건 모른척 해주세요

dfs 탐색 시작을 어디에서 시작해도 상관없다.

임의로 1번 노드에서부터 하기로 한다.

 

 

각각의 노드에 도착했을 때의 거리 합을 구해보면 다음과 같다. 

5번 노드에 도착했을 때가 최대거리이다.

 

그러면 가중치 최대합이 달성되는 노드를 쉽게 찾을 수 있다. 

 

// 최대값과 최대값 시점 말단 노드 갱신
if (max_cost < cost)
{
    max_cost = cost;
    end_node = now;
}

위 코드처럼, 최대값이 갱신될 때마다 end_node를 갱신므로,

결국 max_cost = 11, end_node = 5가 된다.

 

 

그러면 저 7번 노드로 가는 가중치의 값을 더 키워보면 end_node가 바뀔까?

예스. 이제 max_cost = 15, end_node = 7이 된다.

 

 

다른 노드에서 시작해도 어쨌든 그 노드에서부터 최대값이 구해지므로,

결과는 같은 end_node가 나온다. 

 

 

그리고 이제 그 end_node로부터 탐색을 시작하는 dfs함수를 한번 더 진행해서 

최대 가중치를 구하면 된다!