deulee의 개발 노트

문제 사이클이 없는 무방향 그래프 트리(tree)가 주어질 때 트리의 지름을 구하는 문제다. 입력 첫째 줄에 노드의 개수 N (1 N; int X, Y, C; int ret; while (1) { if (!(std::cin >> X >> Y >> C)) break ; varr[X].push_back(P(Y, C)); varr[Y].push_back(P(X, C)); } dfs(1, 0); std::memset(cache, 0, sizeof(cache)); maxDis = 0; dfs(maxNode, 0); std::cout

알고리즘/문제 2023. 5. 24. 18:56

우선 선형 시간안에 트리의 지름을 구하는 방법은 다음과 같다. 트리에서 임의의 정점 X를 정한다. 정점 X에서 가장 먼 정점 Y를 구한다. 정점 Y에서 가장 먼 정점 Z를 구한다. 즉, 트리의 지름은 정점 Y와 정점 Z 사이의 거리를 의미한다. 이를 증명하는 방법은 다음과 같다. 증명 만약 트리에서 정점 U와 정점 V를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 X를 정하고, X에서 가장 먼 정점 Y를 찾았을 때, 아래와 같이 경우를 만들 수 있다. X가 U 혹은 V인경우 Y가 U 혹은 V인경우 X, Y, U, V가 서로 다른 경우 이 경우 1, 2번은 무조건 올바르게 작동할 수 밖에 없다. 그야 DFS 알고리즘에 의해서 당연히 성립될 수 밖에 없다. 그럼 문제는 3번의 경우이다. 3번의 ..

알고리즘/이론 2023. 5. 20. 18:33