알고리즘 별 문제 정리/트리 (2) 썸네일형 리스트형 [C++] 백준 1167: 트리의 지름 문제 이해- 트리의 지름: 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것- 트리의 지름을 구하라 - 시간 제한: 2초- 메모리 제한: 256MB - V: 정점의 개수 (2 ~ 100,000, 10^5)- V개의 줄에 걸쳐 간선의 정보(시작 정점, 종료 정점, 정점까지의 거리)※ 거리 (1 ~ 10,000, 10^4)※ 각 줄의 마지막에는 -1이 입력으로 들어온다. - 트리의 지름을 출력하라. 문제 풀이이 문제는 트리의 지름과 관련된 정보를 알아야 풀 수 있다.임의의 정점에서 거리가 가장 먼 정점은 지름을 구성하는 한 정점이다.또한 지름을 구성하는 정점에서 거리가 가장 먼 정점또한 지름을 구성하는 정점이다. 위 정보만 알고 있다면 다들 쉽게 푸실거라 생각한다. 주의할 점1. 인접 그래프에 입력값을.. [C++] 백준 1068: 트리 문제 이해- 리프 노드: 자식의 개수가 0인 노드- 트리가 주어졌을 때, 노드 1개를 지울 것이다.- 남은 트리에서 리프 노드의 개수를 구하라.※ 단, 노드를 지울경우 그 노드와 노드의 모든 자손이 트리에서 제거된다. - 시간 제한: 2초- 메모리 제한: 128MB - N: 트리의 노드의 개수 (1 ~ 50)- 각 노드의 부모※ 부모가 없을경우, -1이 주어진다.- 지울 노드의 번호 - 노드를 지운 후 리프 노드의 개수 문제 풀이이 문제의 핵심은 그래프의 방향성에 있다고 생각한다. 보통의 트리 문제는트리도 결국 그래프의 일종이니만큼 정점을 인접 그래프로 표현할 때,양방향으로 집어넣는다. 하지만, 이 문제의 경우 리프 노드, 즉 제일 아래의 노드가 우리의 관심사이고위로 올라갈 필요는 전혀 없다.아니,.. 이전 1 다음
