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

문제

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

1167번: 트리의 지름

 

문제풀이

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

1967번 문제도 트리와 지름을 구하는 문제이다. 정점의 최대 개수가 적기 때문에 안 풀었다면 먼저 푸는 것을 추천한다.

 

https://githubseob.tistory.com/27

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

이 문제풀이와 다르게 트리의 지름을 구하는 공식을 이용했다.

임의의 점에서 최장 거리를 구하고, 최장 거리인 정점에서 최장 거리를 구하면 그게 바로 트리의 지름이다.

원래는 1967번처럼 트리의 끝 정점을 구하고 거기서 반대 끝 정점까지의 거리를 구하는 식으로 했다.

visit벡터를 2차원으로 선언하면 메모리 초과, 

1차원으로 선언할 때는 1-2-3을 방문하였으면 3-2-1을 방문 못하는 식으로 했지만 내 실력 내에서 무슨 수를 쓰더라도 시간 초과가 뜨길래 포기하고 질문글을 보다가 공식이 있다는 것을 보고 그걸 이용했다.

 

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

tree의 형태는 이런 식이다.

max_dist는 전역 변수로 선언하여 값을 항상 비교하여 최댓값을 저장하도록 한다.

트리를 한 점에서 돌고, 또 그 점에서 돌아야 하므로

max_node를 트리를 한번 돌고 나왔을 때 최장거리인 시작 정점이 아닌 다른 정점을 저장하는 변수이다.

 

	int current_node = 0;
	int linked_node = 0;
	int num = 0;
	int first = 0;

current_node 노드는 현재 위치, linked_node는 현재 노드와 연결된 노드, num은 가중치, first는 2번의 DFS 중 첫 번째 DFS를 시작하는 정점을 나타내는 변수이다.

 

	for (y = 1; y <= V; ++y) {
		cin >> current_node;
		while (1) {
			cin >> linked_node;
			if (linked_node == -1) break;
			cin >> num;
			tree[current_node].push_back({ linked_node,num });
		}
		if (tree[current_node].size() == 1) first = current_node;
	}

먼저 현재 노드를 입력받는다.

현재 노드를 입력받는 이유는 예제에서는 오름차순으로 입력했지만, 항상 그렇다는 법이 없기 때문이다.

-1을 입력받으면 정점과 가중치를 그만 입력받는다.

좀 더 효율적으로 하기 위해 트리의 끝 정점(연결된 노드가 1개뿐인 정점)에서 시작하려고 first값을 입력받았다.

하지만 작동이 짧기 때문에 이 문제에서는 차이점이 없는 것 같다.

 

	Move(first, 0);
	fill(visit.begin(), visit.end(), false);
	Move(max_node, 0);

입력이 끝났으면 거리를 0으로 초기화하고, DFS함수인 Move함수를 first정점부터 시작한다.

한 번의 순회가 끝났으면 visit함수를 초기화하고 first정점과 최장 거리인 max_node부터 Move함수를 실행한다.

 

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

DFS함수인 Move함수이다. start정점부터 시작하여 distance를 갱신한다.

만약 max_dist에 저장된 값보다 현재 distance가 크면 값을 바꾼다.

tree[start]크기 만큼 돌면서 현재 노드와 연결된 노드들을 방문한 적이 없으면 방문하고 Move함수를 실행한다.

모든 정점을 방문했으면 함수가 종료되고 max_dist에는 최장 거리, max_node는 첫 시작한 정점이 아닌 최장거리인 정점의 값이 저장된다.

 

cout << max_dist;

큰 2번의 Move함수 실행이 종료되었으면 최장거리를 출력한다.

 

코드

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

using namespace std;
int V;
vector<pair<int, int>>tree[100001];
vector<bool>visit;
int max_dist;
int max_node;

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


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

	cin >> V;
	visit = vector<bool>(V + 1, 0);

	for (y = 1; y <= V; ++y) {
		cin >> current_node;
		while (1) {
			cin >> linked_node;
			if (linked_node == -1) break;
			cin >> num;
			tree[current_node].push_back({ linked_node,num });
		}
		if (tree[current_node].size() == 1) first = current_node;
	}


	Move(first, 0);
	fill(visit.begin(), visit.end(), false);
	Move(max_node, 0);

	cout << max_dist;
}