Baekjoon 1967 트리의 지름
2019. 4. 21.
Link https://www.acmicpc.net/problem/1967 소스결과 2700 KB / 4 ms 언어 C++ 출처 Baekjoon 분류 BFS, 트리 설명 트리의 최대 지름을 출력해주자. 어떤 경우가 트리의 지름이 최대가 되는지를 생각하는 것이 가장 어려운문제. 질문 게시판에서 해답을 얻었던 문제. 루트노드에서 갈 수 있는 최장 거리 노드는 무조건 리프노드가 된다. 그렇다면 최장 거리에 있는 리프노드를 기준으로 가장 멀리 있는 다른 노드를 찾는다면 최장 지름을 얻을 수 있다. 해당 아이디어만 있으면 됬던 문제. 떠올리지 못했던 것이 조금 아쉽다. 알고리즘 1. 노드와 간선 정보를 입력 받는다. 2. 1번 노드(root Node)를 기준으로 가장 멀리있는 노드를 구한다. 3. 구해진 노드를 ..
