[백준/알고리즘] 1967번 트리의 지름 (골드 3)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 1967번

 

트리가 주어진다.
트리에서 임의의 두 점 사이의 거리 중 가장 긴 거리인 트리의 지름을 구하시오.

 

풀이 알고리즘 : DFS

 

1167번을 공부하기 위해서 알고리즘을 찾아봤더니, 놀랍게도 트리의 지름에 대한 알고리즘이 있었다!

 

증명을 제외하고 알고리즘만 설명하면,

 

임의의 한 점에서 가장 멀리 있는 점 le를 구하고, le에서 가장 멀리 있는 점 ri를 구하면, le과 ri 사이의 거리가 트리의 지름이다.

라고 할 수 있다.

 

그래서 1번 노드에서 시작하여 첫번째 점 le를 구하고, 똑같이 le에서 시작하여 두번째 점 ri를 구하였고, DFS 알고리즘을 사용하여 구하였다.

 

아래는 정답코드이다.

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// int pair 간단히
#define pii pair<int, int>
#define mp(X, Y) make_pair(X, Y)

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

/*

 백준 1167번

 입력
v : 정점의 개수
adj : 인접 리스트, adj[1] = <2,5> : 1에서 2로 가는 거리가 5

 알고리즘
이번에 새로 공부하게 된 알고리즘
임의의 한 정점에서 가장 먼 거리의 정점을 구하면, 그 정점은 트리의 지름을 이루는 두 노드 중 하나가 된다.
따라서 해당 노드에서 다시 가장 먼 정점을 구하면, 트리의 지름이 된다.

*/

int v;
bool check[100000 + 1];
vector<pii> adj[100000 + 1];

pii dfs(int cur, int difs) {
	int max_node_dif = 0, max_node = 0, node_cnt = 0;
	
	// 방문체크
	check[cur] = true;

	// 연결되어있는 방문하지 않은 모든 노드에 방문하여 최댓값을 찾음.
	for(int i = 0; i < adj[cur].size(); i++) {
		pii next = adj[cur][i];
		if(!check[next.first]) {
			node_cnt++;
			pii move_next = dfs(next.first, difs + next.second);
			if(max_node_dif < move_next.second) {
				max_node_dif = move_next.second;
				max_node = move_next.first;
			}
		}
	}

	if(node_cnt == 0) {
		return mp(cur, difs);
	} else {
		return mp(max_node, max_node_dif);
	}
}

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> v;

	for(int i = 0; i < v; i++) {
		int stt, dst, dist;
		cin >> stt >> dst;
		do {
			cin >> dist;
			adj[stt].push_back(mp(dst, dist));
			cin >> dst;
		} while(dst != -1);
	}

	pii le = dfs(1, 0);
	memset(check, 0, sizeof(check));
	pii ri = dfs(le.first, 0);

	cout << ri.second;

	return 0;
}