백준 1967. 트리의 지름 [성공]

1.문제 해결 전략

저번 문제와 일치하는 문제. 겨우겨우 기억을 더듬어서 풀었던 것 같다. 트리의 지름은 가중치가 주어진 트리에서 한 점(어떤 점이든 상관없음)을 잡고 가장 가중치가 큰 지점까지 dfs를 돈다. 정확히는 가장 가중치가 큰 노드를 기록한후 dfs를 종료시키고 모든 방문 기록을 지운후 가중치가 큰 노드를 시작지점으로 다시 dfs를 돌면 트리의 지름이 나온다. 실제 공식으로 존재하기 때문에 외워두는게 좋을 것 같다.

 

2.작성 코드

#include <iostream>
#include <vector>
#include <memory.h>
// dfs 2번 이용하면됨
using namespace std;
int n;
struct Node {
	int num;
	int value;
};
vector<Node> v[10001];
bool visit[10001] = { false, };
int maxlength = 0;
int onePoint = 0;
void dfs(int n, int length) {
	if (visit[n])return;
	visit[n] = true;

	if (maxlength <= length) {
		maxlength = length;
		onePoint = n;
	}

	for (int i = 0; i < v[n].size(); i++) {
		Node next = v[n][i];
		dfs(next.num, length + next.value);
	}
}

int main()
{
	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		Node node, pnode;
		int parent, num, value;
		cin >> parent >> num >> value;
		node.num = num; node.value = value;
		pnode.num = parent; pnode.value = value;

		v[node.num].push_back(pnode);
		v[parent].push_back(node);
	}

	dfs(1, 0);
	memset(visit, false, sizeof(visit));
	dfs(onePoint, 0);

	cout << maxlength << endl;
}

3.걸린 시간 & 느낀점

25분정도 걸렸다. 4일정도 된 것 같은데.. 방법은 기억이 났는데 확신이 안섰다.

그리고, memset을 사용하려면 memory.h 파일을 포함시켜야한다. 백준에서 memset을 인식 못하는듯 ㅠ