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

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

 

 

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

1967번: 트리의 지름

---

 

해결전략

 

깊이우선탐색 DFS

---

 

정답코드

 

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

struct Node {
	int next;
	int cost;
};

int n;
int maxCost, maxNode; // maxCost: 최대 비용, maxNode: 최대 비용을 가지는 노드 번호
vector<vector<Node>> v;
//vector<Node> v[n]; // 위와 같음
vector<int> ch; // 방문체크

void DFS(int cur, int cost) // 현재 노드(cur), 현재까지의 비용(cost)
{
	ch[cur] = 1; // 현재 노드를 방문 처리

	// maxCost를 업데이트. 기존의 최대 비용보다 현재 비용이 더 크다면, 현재 비용과 현재 노드를 최대 비용과 최대 비용 노드로 갱신
	if (maxCost < cost) {
		maxCost = cost;
		maxNode = cur;
	}

	// 현재 노드에 연결된 모든 노드를 순회
	for (int i = 0; i < v[cur].size(); i++) 
	{
		int next = v[cur][i].next;

		if (ch[next] == 0) { // 다음 노드가 방문되지 않았다면, 해당 노드로 DFS를 재귀 호출
			DFS(next, cost + v[cur][i].cost);
		}
	}
}

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

	cin >> n;
	v.resize(n+1); // 노드 번호가 1부터 시작하므로 n+1로 변경
	ch.resize(n+1);

	int a, b, cost;
	for (int i = 0; i < n-1; i++) { // 트리이므로 n-1개의 간선이 존재
		cin >> a >> b >> cost;
		v[a].push_back({ b, cost });
		v[b].push_back({ a, cost });
	}

	maxCost = 0; // 최대 비용을 저장할 변수를 0으로 초기화
	maxNode = 1; // 시작 노드를 1로 초기화(노드 번호가 1부터 시작하는 경우)

	DFS(1, 0); // 1번 노드부터 탐색 시작

	fill(ch.begin(), ch.end(), 0); // 방문 체크 배열을 0으로 초기화
	maxCost = 0; // 최대 비용을 저장할 변수를 0으로 초기화

	DFS(maxNode, 0); // 가장 멀리 있는 노드부터 다시 탐색 시작

	cout << maxCost << "\n";

	return 0;
}

 

 

 

 

---