[G2] 백준 1167번 트리의 지름 C++ 트리, DFS, 깊이 우선 탐색

리뷰

 

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

간선의 가중치가 있는 트리에서 두 노드의 거리가 가장 큰 길이를 구하는 문제

 

전역 변수

• n : 노드의 개수를 저장할 정수형 변수
• far_node : 첫 번째 dfs를 수행했을 때 가장 먼 거리를 가진 노드의 번호를 저장할 정수형 변수
• max_dist : 각 dfs마다 가장 먼 거리를 식별하기 위한 정수형 변수
• v : 깊이 우선 탐색을 할때 방문 처리를 확인하기 위한 정수형 배열, 크기는 100001로 초기화 한다.
• Edge : 노드의 자식과 간선의 가중치를 저장하기 위한 구조체
• edges : 각 노드의 인접리스트를 저장하기 위한 Edge타입 벡터, 크기는 100001로 초기화 한다.

 

함수

1. dfs

void dfs(int node, int dist)

 

깊이 우선 탐색을 통해 가장 먼 노드와 거리를 구하기 위한 함수

1. 매개변수로 node, dist를 받는다. node는 현재 재귀단계에서의 노드고, dist는 간선 가중치의 합이다.
2. 만약 max_dist보다 dist가 크다면 max_dist를 dist로 바꾸어 주고, far_node를 node로 바꾸어 준다.
3. 인접 리스트를 순회하며 방문하지 않은 노드라면 방문처리 후 재귀를 진행해 준다.

 

문제풀이

1. n값을 입력 받고, n개의 노드에 간선 정보를 받아 인접리스트를 초기화 해준다.
2. 노드 1에 방문처리를 하고 1을 루트로 dfs를 진행해 준다.
3. 이제 fat_node에 저장된 노드를 통해 dfs를 한번 더 진행해 주어야 한다.
4. max_dist와 방문배열을 모두 0으로 초기화 해주고 far_node에 방문처리 후 dfs를 진행해 준다.
5. max_dist에 저장된 값을 출력해 준다.

 

참고 사항

첫번째 dfs에서는 임의의 루트 1에서 가장 먼 노드를 찾아준다.

위에서 찾은 노드를 루트로 하는 dfs를 돌리면 트리의 지름을 알 수 있다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

int n, far_node, max_dist;
int v[100001];

struct Edge {
	int c, d;
};

vector<Edge> edges[100001];

void dfs(int node, int dist) {
	if (max_dist < dist) {
		max_dist = dist;
		far_node = node;
	}

	for (Edge edge : edges[node]) {
		int c = edge.c, d = edge.d;
		if (v[c]) continue;
		v[c] = 1;
		dfs(c, dist + d);
	}
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int cur; cin >> cur;
		while (1) {
			int next; cin >> next;
			if (next == -1) break;
			int w; cin >> w;
			edges[cur].push_back({ next, w });
		}
	}
	v[1] = 1;
	dfs(1, 0);

	max_dist = 0;
	memset(v, 0, sizeof(v));
	v[far_node] = 1;
	dfs(far_node, 0);

	cout << max_dist;
}