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

 

1967번: 트리의 지름

이전에 풀었던 같은 이름의 문제(https://www.acmicpc.net/problem/1167)와 많이 유사한 문제다.

이 문제를 풀려고 오랫동안 고민했지만 풀이가 떠오르지 않아서 다음 블로그를 참고했다.

https://lmcoa15.tistory.com/56

백준 1967번 - 트리의 지름

수학적인 사고가 필요한 문제인 것 같다.

아무 노드 하나를 잡고 그 노드에서 제일 먼 노드,

그리고 그 노드에서 제일 먼 노드. 그렇게 계산된 두 거리 중 긴 거리가 트리의 지름이라는데, 와닿지는 않는다.

위 방법대로 깊이 우선 탐색을 두 번 실행하면 해결이다. 

첫 번째 제출에서는 OutOfBounds라는 런타임에러가 발생했다.

질문에서 알아보니, n = 1일 때를 고려하지 않아 인덱싱에서 오류가 발생했다.

글 읽기 - dfs 로 하면 런타임 오류 뜹니까??

정확히는 간선의 정보를 n - 1번 입력 받아야 하지만 n번 입력을 받으면서 문제가 발생했다.

테스트를 해보니, 입력 파일엔 더 이상의 입력이 없는데 더 받으려 하면 마지막 입력 값이 반복되어 저장되는 것 같다.

이를 수정하고 제출하니 AC를 받았다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int n;
	cin >> n;
	vector<vector<pair<int, int>>> adj(n);
	FOR(i, n - 1) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u - 1].push_back(make_pair(v - 1, w));
		adj[v - 1].push_back(make_pair(u - 1, w));
	}

	int first_max = 0;
	int first_max_dest = 0;
	stack<pair<int, int>> dfs;
	vector<bool> mark(n, false);
	dfs.push(make_pair(0, 0));
	mark[0] = true;
	while (!dfs.empty()) {
		auto [here, cost] = dfs.top();
		if (cost > first_max) {
			first_max = cost;
			first_max_dest = here;
		}
		dfs.pop();
		for (auto& a : adj[here])
			if (!mark[a.first]) {
				dfs.push(make_pair(a.first, cost + a.second));
				mark[a.first] = true;
			}
	}

	int second_max = 0;
	dfs = stack<pair<int, int>>();
	mark = vector<bool>(n, false);
	dfs.push(make_pair(first_max_dest, 0));
	mark[first_max_dest] = true;
	while (!dfs.empty()) {
		auto [here, cost] = dfs.top();
		second_max = cost > second_max ? cost : second_max;
		dfs.pop();
		for (auto& a : adj[here])
			if (!mark[a.first]) {
				dfs.push(make_pair(a.first, cost + a.second));
				mark[a.first] = true;
			}
	}

	cout << (first_max > second_max ? first_max : second_max) << EL;

	return 0;
}