[백준 1167 | C++] 트리의 지름 :: 트리의 지름

• 문제 링크 : 1167번: 트리의 지름
• 관련 태그 : 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색
• 참고 자료 : 

2025.01.05 - [STUDY/Algorithm] - [알고리즘] Diameter of Tree : 트리의 지름

[알고리즘] Diameter of Binary Tree : 트리의 지름

 

풀이

dfs를 두 번 돌리면 됩니다. 백준 1967과 입력 형식만 다르게 풀이 완전 동일

코드

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

// DFS를 사용하여 시작 노드에서 가장 먼 노드와 그 거리를 반환하는 함수
pair<int, int> dfs(int start, int n, vector<vector<pair<int, int>>>& adj) {
	
	// 각 노드까지의 거리를 저장 (-1은 아직 방문하지 않음을 의미)
	vector<int> dist(n + 1, -1);
	stack<int>stk;

	stk.push(start);
	dist[start] = 0;

	while (!stk.empty()) {
		int tmp = stk.top();
		stk.pop();

		for (auto x : adj[tmp]) {
			if (dist[x.first] == -1) {	// 처음 방문이라면
				stk.push(x.first);
				dist[x.first] = dist[tmp] + x.second;
			}
		}
	}

	int idx = 0;
	int m = dist[0];
	for (int i = 0;i < n + 1;i++) {
		if (m < dist[i]) {
			m = dist[i];
			idx = i;
		}		
	}

	return { idx, m };	// idx : 가장 먼 노드, m : 그 거리
}

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

	int n;
	cin >> n;

	vector<vector<pair<int, int>>>adj(n + 1);

	int p, c, w;   // parent, child, weight
	int t;
	for (int i = 1; i < n;i++) {
		cin >> p;	// 트리의 정점 번호 입력
		cin >> t;
		while (t != -1) {
			c = t;
			cin >> w;
			adj[p].push_back({ c, w });
			adj[c].push_back({ p, w });

			cin >> t;
		}
	}

	int node, res;
	node = dfs(1, n, adj).first;
	res = dfs(node, n, adj).second;

	cout << res;
}