1167번 (gold 2)

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

탐색을 이용한 조금 복잡한 문제를 풀어보았다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
static bool print = false;
int BFS(vector<vector<pair<int, int>>>&, int);
int main() { 

	int N;
	cin >> N;
	vector<vector<pair<int, int>>> arr(N + 1);
	for (int i = 1; i <= N; ++i) {
		int node = 0, edge = 0, index = 0;
		cin >> index;
		while (true) {
			cin >> node;
			if (node != -1) {
				cin >> edge;
				if (edge != -1) {
					arr[index].emplace_back(make_pair(node, edge));
				}
				else
					break;
			}
			else
				break;
		}

		
	}
	BFS(arr, BFS(arr, 1));

	return 0;
}

int BFS(vector<vector<pair<int, int>>>& arr, int n) {
	queue<int> q({ n });
	vector<bool> visit(arr.size(), false);
	visit[n] = true;
	vector<int> edge_len(arr.size(), 0);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (int i = 0; i < arr[node].size(); ++i) {
			int n = arr[node][i].first, e = arr[node][i].second;
			if (visit[n] == false) {
				visit[node] = true;
				q.push(n); edge_len[n] = edge_len[node] + e;
			}
		}
	}
	int compare_num = 0, node_tmp = 0;
	for (int i = 1; i < edge_len.size(); ++i) {
		if (edge_len[i] > compare_num) {
			compare_num = edge_len[i];
			node_tmp = i;
		}
	}
	if (print == true) {
		cout << compare_num;
	}
	print = true;
	return node_tmp;
}

트리 구조에서 가장 긴 경로를 찾으려면 루트 - 리프 혹은 리프 - 리프여야 한다. 왜냐하면 트리의 임의의 두 노드가 가장 긴 경로가 되려면 두 노드 모두 끝 부분에 위치해야 하기 때문이다. 중간에 내부 노드라면 결국 부모 노드와 자식 노드가 내부 노드에 연결되어 있을텐데 그러면 가장 긴 경로가 되지 못한다.(추가로 더 멀어질 수 있는 노드가 있기 때문)

 

또한 임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 지름에 해당하는 두 노드 중 하나일 것이다.