(백준 1967번 트리 지름 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 3 with gpt

풀이가 감이 오질 않아 gpt에게 물어보고 나름 내 스타일대로 풀어보았다. 

 

백준 1967번

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

 

트리에서 가장 긴 거리를 구하는 문제인데, gpt는 2번의 dfs방법을 사용해서 풀었다.

보고나니 당연하게 느껴졌지만, 처음에는 생각하지 못했다..ㅠ

 

우선 가장 긴 거리는 당연히! leaf에서 출발해서 leaf에서 끝날 것이다..!

그렇다면 우선 root에서 시작에서 가장 멀리 있는 leaf를 찾은 다음( = farthestNode)

farthestNode에서 다시 dfs를 통해 가장 멀리 있는 leaf를 찾으면 된다.

 

여기서 신박했던 점은 farthestNode와 maxDistance를 찾는 방법이다.

dfs 매 실행마다 farthestNode와 maxDistance를 업데이트하는 방법을 사용한다.

 

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

constexpr int MAX_N = 10000 + 1;
vector<pair<int, int>> adj[MAX_N];
vector<bool> visited = { false };

int farthestNode = 0;
int maxDistance = 0;

void dfs(int node, int distance) {
	visited[node] = true;
	if (distance > maxDistance) {
		maxDistance = distance;
		farthestNode = node;
	}

	for (auto next : adj[node]) {
		int nextNode = next.first;
		int weight = next.second;
		if (!visited[nextNode]) {
			dfs(nextNode, distance + weight);
		}
	}

	return;
}


int main() {
	int n, u, v, w; cin >> n;
	visited.resize(n+1);

	for (int i = 1; i < n; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v, w });
		adj[v].push_back({ u, w });
	}

	fill(visited.begin(), visited.end(), false);
	dfs(1, 0);
	int startNode = farthestNode;
	maxDistance = 0;

	fill(visited.begin(), visited.end(), false);
	dfs(startNode, 0);

	cout << maxDistance;


}

 

 

어떻게 푸는지 상당히 오래 고민한 문제...

gpt가 진짜 몇 년만 더 있으면 나보다 더 많은걸 하는 시대가 올 텐데.. 껄껄