알고리즘 공부/C++
[G4] 백준 1967번 트리의 지름 C++ DFS, 트리
마달랭
2024. 11. 18. 09:12
리뷰
https://www.acmicpc.net/problem/1967
간선의 가중치가 있는 트리에서 가장 먼 노드끼리의 길이를 구하면 트리의 지름이 된다.
유사문제로는 BOJ 1167번이 있다.
https://www.acmicpc.net/problem/1167
전역 변수
- n : 노드의 개수
- v : 방문 처리 배열
- Edge : 간선을 나타낼 구조체, 다음 노드 nxt와 가중치 val값을 가진다.
- lst : 인접 리스트를 저장할 Edge타입 2차 벡터
- result : 시작 노드로 부터 가장 먼 노드와 그 때의 가중치를 저장할 정수형 2개의 pair
함수
1. dfs
void dfs(int node, int val)
깊이 우선 탐색을 통해 트리의 지름을 구하기 위한 함수
- 매개변수로 탐색을 진행할 노드 node와 현재 까지의 가중치 val를 입력 받는다.
- 만약 result의 second값이 val보다 작다면 result를 node와 val로 최신화 해준다.
- node의 인접리스트를 순회하며 다음 노드가 방문처리가 되어있지 않다면 방문 처리 후 재귀를 실행한다.
- 재귀를 실행할 때 매개변수로 다음 노드와 간선의 가중치를 val에 더해서 진행해 준다.
문제풀이
- n값을 입력 받고, 인접 리스트 lst를 n + 1크기로 resize해준다. (1-based-index 이기 때문)
- n - 1개의 간선 정보를 양방향 간선으로 인접 리스트 lst에 초기화 해준다.
- 1번 노드를 방문처리 후 dfs를 실행해 준다.
- 방문배열을 초기화 하고 result의 first, 즉 result에 저장된 노드를 방문처리 해준다.
- 마찬가지로 result의 first를 통해 dfs를 실행해 준다.
- 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;
}
728x90