두 나무를 병합한 후 최소 지름 찾기

3203. 두 나무를 병합한 후 최소 지름 찾기

난이도:어려움

주제: 트리, 깊이 우선 검색, 너비 우선 검색, 그래프

각각 0에서 n - 1, 0에서 m - 1까지 번호가 매겨진 n 및 m 노드를 갖는 두 개의 무방향 트리가 있습니다. 길이가 각각 n - 1 및 m - 1인 두 개의 2D 정수 배열 edge1 및 edge2가 제공됩니다. 여기서 edge1[i] = [a_i, b_i]는 다음을 나타냅니다. 첫 번째 트리의 노드 a_i와 b_i 사이의 간선이고 edge2[i] = [u_i, v_i]는 두 번째 트리의 노드 u_i와 v_i 사이에 간선이 있음을 나타냅니다.

첫 번째 트리의 한 노드를 에지로 두 번째 트리의 다른 노드와 연결해야 합니다.

결과 트리의 최소가능한 직경을 반환합니다.

트리의 직경은 트리의 두 노드 사이의 가장 긴 경로의 길이입니다.

예 1:

• 입력: edge1 = [[0,1],[0,2],[0,3]], edge2 = [[0,1]]
• 출력: 3
• 설명: 첫 번째 트리의 노드 0을 두 번째 트리의 노드와 연결하면 직경 3의 트리를 얻을 수 있습니다.

예 2:

• 입력: edge1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2, 7]], edge2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
• 출력: 5
• 설명: 첫 번째 트리의 노드 0을 두 번째 트리의 노드 0과 연결하면 직경 5의 트리를 얻을 수 있습니다.

제약조건:

• 1 5
• edges1.length == n - 1
• edges2.length == m - 1
• 가장자리1[i].길이 == 가장자리2[i].길이 == 2
• edges1[i] = [a_i, b_i]
• 0 i, b_i
• edges2[i] = [u_i, v_i]
• 0 i, v_i
• edge1과 edge2가 유효한 트리를 나타내도록 입력이 생성됩니다.

힌트:

1. tree1의 노드 a를 tree2의 노드 b와 연결했다고 가정합니다. 결과 나무의 직경 길이는 다음 3가지 값 중 가장 큰 값이 됩니다.
   1. 나무의 지름 1.
   2. 나무의 지름 2.
   3. 노드 a에서 시작하여 완전히 트리 1 내에 포함되는 가장 긴 경로의 길이 노드 b에서 시작하여 완전히 트리 2 1 내에 포함되는 가장 긴 경로의 길이
   4. 세 번째 값에 추가된 값은 트리 1과 2 사이에 추가한 가장자리 때문입니다.
2. a와 b를 선택하더라도 값 1과 2는 일정합니다. 따라서 값 3이 최소화되는 방식으로 a와 b를 선택해야 합니다.
3. a와 b를 최적으로 선택하면 각각 Tree 1과 Tree 2의 직경이 됩니다. 정확히 어떤 직경의 노드를 선택해야 할까요?
4. a는 나무 1의 지름 중심이고, b는 나무 2의 지름의 중심입니다.

해결책:

나무의 지름을 계산하는 방법과 두 나무를 연결하는 것이 전체 지름에 어떤 영향을 미치는지 이해하는 데 중점을 두고 단계별로 접근해야 합니다.

해결 단계:

1. 각 나무의 지름 찾기:

   • 나무의 지름은 두 노드 사이의 가장 긴 경로입니다. 이를 찾으려면 다음과 같은 2단계 프로세스를 사용할 수 있습니다.
     1. 임의의 노드에서 BFS(또는 DFS)를 수행하여 가장 먼 노드를 찾습니다(이 노드를 A라고 하겠습니다).
     2. A에서 시작하여 또 다른 BFS(또는 DFS)를 수행하여 A에서 가장 먼 노드(이 노드를 B라고 함)를 찾으면 A에서 B까지의 거리가 트리의 지름이 됩니다.

2. 연결할 최적의 노드 결정:

   • 문제의 힌트에서 두 나무를 연결할 때 추가 직경을 최소화하는 가장 좋은 방법은 두 나무 직경의 중심을 연결하는 것입니다. 이렇게 하면 새 가장자리로 인해 발생하는 가장 긴 경로가 최소화됩니다.
   • 나무 직경의 최적 노드는 일반적으로 직경의 끝점에서 BFS를 수행하고 가장 긴 경로의 중간을 찾아 찾을 수 있는 "중심"입니다.

3. 전체 직경 최소화:

   • 두 나무의 중심을 찾으면 새 지름은 다음의 최대값이 됩니다.
     • 나무 1의 지름.
     • 나무 2의 지름.
     • 트리 1 내에서 가장 긴 경로, 트리 2 내에서 가장 긴 경로, 새 연결 가장자리에 대한 1의 합입니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3203. 두 나무를 병합한 후 최소 직경 구하기

<?php /**
 * @param Integer[][] $edges1
 * @param Integer[][] $edges2
 * @return Integer
 */
function minimumDiameterAfterMerge($edges1, $edges2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to find the diameter of a tree and the farthest node from a start node
 *
 * @param $n
 * @param $edges
 * @param $start
 * @return array
 */
function bfs($n, $edges, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to find the diameter of a tree and its center
 *
 * @param $n
 * @param $edges
 * @return array
 */
function getDiameterAndCenter($n, $edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$edges1 = [[0,1],[0,2],[0,3]];
$edges2 = [[0,1]];
echo minimumDiameterAfterMerge($edges1, $edges2);  // Output: 3

// Example 2
$edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]];
$edges2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]];
echo minimumDiameterAfterMerge($edges1, $edges2);  // Output: 5
?>

설명:

1. BFS 도우미 함수: bfs 함수는 주어진 시작 노드에서 가장 먼 노드를 계산하고 거리 배열과 찾은 가장 먼 노드를 반환합니다. 이는 나무의 지름을 계산하는데 필수적입니다.

2. 직경 및 중심 가져오기: getDiameterAndCenter 함수는 나무의 직경과 중심을 찾습니다. 두 나무를 병합할 때 새 나무의 직경을 최소화하려면 나무의 중심이 중요합니다.

3. 주요 솔루션:

   • 먼저 두 트리에 대한 인접 목록을 작성합니다.
   • 두 나무의 지름과 중심을 계산합니다.
   • 각 트리 내에서 가장 긴 경로를 얻기 위해 두 트리의 중심에서 BFS를 수행합니다.
   • 마지막으로 세 가지 값 중 최대값을 계산하여 병합된 트리의 최소 직경을 얻습니다.

시간 복잡도:

• 인접 목록 구성: O(n m)
• BFS 순회: O(n·m)
• 전체 시간 복잡도는 O(n·m)이며, 이는 입력 크기 제한 10⁵에 효율적입니다.

이 접근 방식을 사용하면 두 나무를 병합할 때 가능한 최소 직경을 찾을 수 있습니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 두 나무를 병합한 후 최소 지름 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!