[BOJ 1167]

문제 바로가기 : https://www.acmicpc.net/problem/1167
유사 문제 : https://www.acmicpc.net/problem/1967

Solution

트리의 지름 구하기

처음 짰을 땐 리프 노드를 미리 담아두고 BFS에 넣어가면서 진행했고 역시나 시간초과를 받았다ㅠㅠ
qna를 찾아보니 트리의 지름을 구하는 정형화된 방법이 이미 있었다!
아무 점에서 시작해 가장 먼 점(re)을 찾고 가장 먼 점에서 시작해 가정 먼 점을 찾으면 트리의 지름이 된다!
다른 곳에서 응용되는 아이디어인거 같다고 언급이 돼있었으니 까먹지 않도록 하자.

review

여느 BFS와 다를 것 없이 시작 점부터 큐에 넣어준다.

void bfs(int s) {
	for(int i=0; i<node[s].size(); i++) q.push({ node[s][i].first, node[s][i].second });
	chk[s] = true;

종료 조건은 리프 노드일 때로 설정했다. 답이 갱신됐으면 그 위치를 기록하도록 했다.
이렇게 최종 기록된 위치 re는 다시 BFS로 들어가 가장 먼 점을 찾아줄 것이다.

//종료 조건
if (node[cur].size() <= 1) {
  ans = max(ans, dist);
  if (ans == dist) re = cur;
  continue;
}