도로 추가 조회 후 최단 거리 I

3243. 도로 추가 조회 후 최단 거리 I

난이도:중

주제: 배열, 너비 우선 검색, 그래프

정수 n과 2차원 정수 배열 쿼리가 제공됩니다.

0부터 n - 1까지 번호가 매겨진 n개의 도시가 있습니다. 처음에는 도시 i에서 도시 i까지 단방향 도로가 있습니다. 모두 0

queries[i] = [u_i, v_i]는 도시 ui단방향 _{도로 추가를 나타냅니다. > v}i _{도시로. 각 쿼리 후에는 도시 0에서 도시 n - 1까지의} 최단 경로의 길이를 찾아야 합니다.

반환

[0, query.length - 1] 범위의 각 i에 대해 답변[i]가 첫 번째 검색어 1개.

예 1:

입력:
• n = 5, 쿼리 = [[2,4],[0,2],[0,4]]
출력:
• [3,2,1]
설명:
• 2에서 4까지의 도로를 추가한 후 0에서 4까지의 최단 경로의 길이는 3이 됩니다. 0에서 2까지의 도로를 추가한 후, 0에서 4까지의 최단 경로의 길이는 2가 됩니다. 0에서 4까지의 도로를 추가한 후 0에서 4까지의 최단 경로의 길이는 1이 됩니다.

예 2:

입력:
• n = 4, 쿼리 = [[0,3],[0,2]]
출력:
• [1,1]
설명:
• 0에서 3까지 도로를 추가한 후 0에서 3까지의 최단 경로 길이는 1이 됩니다. 0에서 2까지 도로를 추가하면 최단 경로의 길이는 1로 유지됩니다.

제약조건:

3

1

쿼리[i].length == 2

0

1

쿼리 중 반복되는 도로는 없습니다.

힌트:

1. 각 업데이트 후에 그래프를 유지하고 효율적인 최단 경로 알고리즘을 사용합니다.
2. 각 쿼리에는 BFS/Dijkstra를 사용합니다.

해결책:

도시 간 도로 추가를 시뮬레이션하고 각 도로 추가 후 도시 0에서 도시 n - 1까지의 최단 경로를 계산해야 합니다. 제약 조건과 문제의 성격을 고려하여 비가중 그래프에 BFS(너비 우선 검색)를 사용할 수 있습니다.

접근하다:

1. 그래프 표현:

   • 인접 목록을 사용하여 도시와 도로를 나타낼 수 있습니다. 처음에, 각 도시 i는 모든 0
   • 각 쿼리 후에 u_i에서 v_i까지의 도로를 그래프에 추가합니다.

2. 최단 경로 계산(BFS):

   • BFS를 사용하여 도시 0에서 도시 n - 1까지의 최단 경로를 계산할 수 있습니다. 모든 도로의 가중치가 동일하기 때문에(각 도로의 길이는 1임) BFS가 여기서 잘 작동합니다.

3. 쿼리 반복:

   • 각 쿼리에 대해 그래프에 새 도로를 추가한 다음 BFS를 사용하여 도시 0에서 도시 n - 1까지의 최단 경로를 찾습니다. 각 쿼리를 처리한 후 결과를 출력 배열에 저장합니다.

4. 효율성:

   • 각 쿼리 후에 BFS를 사용하고 그래프 크기는 최대 500개의 도시, 최대 500개의 쿼리가 될 수 있으므로 각 BFS의 시간 복잡도는 O(n·m)입니다. 여기서 n은 도시의 수이고 m은 도로의 수. BFS를 최대 500회까지 수행해야 솔루션이 문제의 제약 조건 내에서 효율적으로 실행됩니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3243. 도로 추가 조회 후 최단 거리 I

<?php /**
 * @param Integer $n
 * @param Integer[][] $queries
 * @return Integer[]
 */
function shortestDistanceAfterQueries($n, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to find the shortest path using BFS
 *
 * @param $graph
 * @param $n
 * @return int
 */
function bfs($graph, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$n = 5;
$queries = [[2, 4], [0, 2], [0, 4]];
print_r(shortestDistanceAfterQueries($n, $queries));

// Example 2
$n = 4;
$queries = [[0, 3], [0, 2]];
print_r(shortestDistanceAfterQueries($n, $queries));
?>

설명:

1. 그래프 초기화:

   • 인접 목록 그래프를 사용하여 도시와 도로를 표현합니다.
   • 처음에는 연속된 도시(i~i 1) 사이에만 도로가 존재합니다.

2. BFS 기능:

   • BFS는 도시 0에서 도시 n - 1까지의 최단 거리를 계산하는 데 사용됩니다. BFS에 대한 대기열과 각 도시에 도달하는 최소 도로(가장자리) 수를 저장하는 거리 배열을 유지합니다.
   • 처음에는 0번 도시까지의 거리가 0으로 설정되어 있고, 그 외 모든 도시의 거리는 무한대(PHP_INT_MAX)입니다.
   • BFS 대기열의 각 도시를 처리하면서 인접 도시의 거리를 업데이트하고 도달 가능한 모든 도시를 방문할 때까지 계속합니다.

3. 쿼리 처리:

   • 각 쿼리에 대해 새 도로가 그래프에 추가됩니다(u -> v).
   • 업데이트 후 도시 0에서 도시 n-1까지의 최단 경로를 계산하기 위해 BFS가 호출됩니다.
   • BFS의 결과는 결과 배열에 저장됩니다.

4. 출력:

   • 결과 배열에는 각 쿼리 후 가장 짧은 경로 길이가 포함됩니다.

5. 시간 복잡도:

   • 각 BFS는 O(n·m)을 차지합니다. 여기서 n은 도시 수이고 m은 도로 수입니다. 쿼리 수가 q개이므로 전체 시간 복잡도는 O(q * (n m))이며 이는 주어진 제약 조건에 효율적입니다.

예제 연습:

입력 n = 5 및 쿼리 = [[2, 4], [0, 2], [0, 4]]:

• 처음에는 도로가 [0 -> 1 -> 2 -> 3 -> 4].
• 첫 번째 쿼리 [2, 4] 이후 도로는 [0 -> 1 -> 2 -> 3 -> 4]이고 0에서 4까지의 최단 경로는 3입니다(경로 0 -> 1 -> 2 -> 4 사용).
• 두 번째 쿼리 [0, 2] 이후 도로는 [0 -> 2, 1 -> 2 -> 3 -> 4], 0에서 4까지의 최단 경로는 2입니다(경로 0 -> 2 -> 4 사용).
• 세 번째 쿼리 [0, 4] 이후 도로는 [0 -> 2, 1 -> 2 -> 3 -> 4], 0에서 4까지의 최단 경로는 1(직통 도로 0 -> 4)입니다.

따라서 출력은 [3, 2, 1]입니다.

최종 생각:

• 이 솔루션은 각 쿼리에 BFS를 사용하여 최단 경로를 효율적으로 계산합니다.
• 각 쿼리에 새로운 도로가 추가될 때마다 그래프가 동적으로 업데이트됩니다.
• 이 솔루션은 문제의 제약 내에서 잘 작동하며 최대 500개 도시에 대한 최대 500개의 쿼리를 효율적으로 처리합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 도로 추가 조회 후 최단 거리 I의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!