C++ / 백준 / 1967 / 트리의 지름

문제

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

1967번: 트리의 지름

문제풀이

트리의 지름을 쉽게 구하는 공식이 있다는 것을 모르는 상태로 단순하게 DFS를 하여 지름을 구하는 방법을 썼다.

노드의 개수가 더 많았으면 시간 초과로 틀릴 알고리즘이다.

 

vector<pair<int, int>>tree[10001];
vector<bool>visit;
int max_dist;

 

tree의 형태는 이런 식이다.

	for (y = 1; y < V; ++y) {
		cin >> current_node;
		cin >> linked_node;
		cin >> num;
		tree[current_node].push_back({ linked_node, num });
		tree[linked_node].push_back({ current_node, num });
	}

메인 문에서 값을 입력받으면 양방향 간선이므로 tree[current_node]에 linked_node와 숫자,

tree[linked_node]에 current_node와 숫자를 입력한다.

	visit = vector<bool>(V + 1, 0);
	for (y = 1; y <= V; ++y) {
		if (tree[y].size() == 1) {
			fill(visit.begin(), visit.end(), 0);
			Move(y, 0);
			tree[y].resize(0);
		}
	}

visit벡터를 1차원으로 선언하였기 때문에 dfs함수인 Move함수를 실행한다.

트리의 최장거리는 연결된 노드가 하나뿐인 노드에서 똑같이 연결된 노드가 하나뿐인 노드의 길이이다.

그래서 tree[y]의 크기가 1인 값을 찾고 visit벡터를 초기화, 함수를 실행하고 같은 끝 노드끼리의 최장거리를 다시는 계산하지 않게 tree[y]의 사이즈를 0으로 줄인다.

예를 들어 1-2-3이 최장거리라 치면 3-2-1의 경우를 못하도록 1을 막아 불필요한 작동을 막는다.

 

void Move(int start, int distance) {
	visit[start] = true;
	for (int cnt = 0; cnt < tree[start].size(); ++cnt) {
		int next_node = tree[start][cnt].first;
		int next_dist = distance + tree[start][cnt].second;
		if (!visit[next_node] && tree[next_node].size() != 0) {
			visit[next_node] = true;
			max_dist = max(max_dist, next_dist);
			Move(next_node, next_dist);			
		}		
	}
}

tree[start]의 크기만큼 반복하면서 다음 노드와 다음 노드와의 거리를 더한 값을 구하고

다음 노드의 사이즈가 0이 아니고 방문한 적이 없는 노드이면 최장거리가 바뀌면 갱신하고, Move함수를 실행한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int V;
vector<pair<int, int>>tree[10001];
vector<bool>visit;
int max_dist;

void Move(int start, int distance) {
	visit[start] = true;
	for (int cnt = 0; cnt < tree[start].size(); ++cnt) {
		int next_node = tree[start][cnt].first;
		int next_dist = distance + tree[start][cnt].second;
		if (!visit[next_node] && tree[next_node].size() != 0) {
			visit[next_node] = true;
			max_dist = max(max_dist, next_dist);
			Move(next_node, next_dist);			
		}		
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int y = 0;
	int current_node = 0;
	int linked_node = 0;
	int num = 0;

	cin >> V;

	for (y = 1; y < V; ++y) {
		cin >> current_node;
		cin >> linked_node;
		cin >> num;
		tree[current_node].push_back({ linked_node, num });
		tree[linked_node].push_back({ current_node, num });
	}

	visit = vector<bool>(V + 1, 0);
	for (y = 1; y <= V; ++y) {
		if (tree[y].size() == 1) {
			fill(visit.begin(), visit.end(), 0);
			Move(y, 0);
			tree[y].resize(0);
		}
	}
	cout << max_dist;
}