[G4] 백준 1967번 트리의 지름 C++ DFS, 트리

리뷰

 

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

간선의 가중치가 있는 트리에서 가장 먼 노드끼리의 길이를 구하면 트리의 지름이 된다.

유사문제로는 BOJ 1167번이 있다.

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

 

 

전역 변수

1. n : 노드의 개수
2. v : 방문 처리 배열
3. Edge : 간선을 나타낼 구조체, 다음 노드 nxt와 가중치 val값을 가진다.
4. lst : 인접 리스트를 저장할 Edge타입 2차 벡터
5. result : 시작 노드로 부터 가장 먼 노드와 그 때의 가중치를 저장할 정수형 2개의 pair

 

함수

1. dfs

void dfs(int node, int val)

 

깊이 우선 탐색을 통해 트리의 지름을 구하기 위한 함수

1. 매개변수로 탐색을 진행할 노드 node와 현재 까지의 가중치 val를 입력 받는다.
2. 만약 result의 second값이 val보다 작다면 result를 node와 val로 최신화 해준다.
3. node의 인접리스트를 순회하며 다음 노드가 방문처리가 되어있지 않다면 방문 처리 후 재귀를 실행한다.
4. 재귀를 실행할 때 매개변수로 다음 노드와 간선의 가중치를 val에 더해서 진행해 준다.

 

문제풀이

1. n값을 입력 받고, 인접 리스트 lst를 n + 1크기로 resize해준다. (1-based-index 이기 때문)
2. n - 1개의 간선 정보를 양방향 간선으로 인접 리스트 lst에 초기화 해준다.
3. 1번 노드를 방문처리 후 dfs를 실행해 준다.
4. 방문배열을 초기화 하고 result의 first, 즉 result에 저장된 노드를 방문처리 해준다.
5. 마찬가지로 result의 first를 통해 dfs를 실행해 준다.
6. result의 second에 저장된 값을 출력해 준다.

 

참고 사항

트리에서의 지름을 구하는 방법은 임의의 노드에서 출발해 가장 먼 노드를 찾아준다.

해당 노드에서 다시 출발하여 가장 먼 노드를 찾는다면 트리의 지름을 구할 수 있다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int n;
int v[10001];
struct Edge {
	int nxt, val;
};
vector<vector<Edge>> lst;
pair<int, int> result;

void dfs(int node, int val) {
	if (result.second < val) result = { node, val };
	for (const Edge& edge : lst[node]) {
		if (!v[edge.nxt]) {
			v[edge.nxt] = 1;
			dfs(edge.nxt, val + edge.val);
		}
	}
}

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

	cin >> n;
	lst.resize(n + 1);
	for (int i = 0; i < n - 1; ++i) {
		int a, b, c; cin >> a >> b >> c;
		lst[a].push_back({ b, c });
		lst[b].push_back({ a, c });
	}

	v[1] = 1;
	dfs(1, 0);

	memset(v, 0, sizeof(v));
	v[result.first] = 1;
	dfs(result.first, 0);

	cout << result.second;
}