지름2 백준 1167 트리의 지름 www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 �� www.acmicpc.net 이 문제도 1967번과 똑같은 문제다. 다만 입력받는 방식이 조금 귀찮아졌다. 마찬가지로 1번 노드에서 DFS를 돌리고 최댓값의 인덱스를 저장해 두었다가 다시 DFS를 돌리면 된다. #include #include #include using namespace std; bool vis[100001]; vector ar[100001]; int ans, idx; void dfs(int cur, int.. 2020. 9. 10. 백준 1967 트리의 지름 www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 �� www.acmicpc.net 무방향 그래프가 가중치를 포함하여 주어진 트리에서 트리의 지름을 구하는 문제이다. 지름은 가중치가 가장 긴 값이 지름이 된다. 문제는 이해가 되는데 트리의 지름에 대한 개념이 없어서 어떻게 풀어야 할지 감이 안 잡혀 다른 분들의 코드를 참고했다. 정해는 부모 노드에서 DFS를 돌려서 가장 큰 값이 나온 그 노드를 저장하고, 그 노드에서 다시 DFS를 돌려서 가장 큰 값이 나온다면 그 값이 지.. 2020. 9. 10. 이전 1 다음