코너 도달을 위한 최소 장애물 제거

2290. 코너 도달을 위한 최소 장애물 제거

난이도:어려움

주제: 배열, 너비 우선 검색, 그래프, 힙(우선순위 큐), 행렬, 최단 경로

인덱스가 0인 m x n 크기의 2D 정수 배열 그리드가 제공됩니다. 각 셀에는 두 가지 값 중 하나가 있습니다.

• 0은 빈 셀
을 나타냅니다.
• 1은 제거할 수 있는 장애물을 나타냅니다.

빈 셀에서 위, 아래, 왼쪽, 오른쪽으로 이동할 수 있습니다.

최소개의 장애물을 제거하여 반환하면 왼쪽 상단(0, 0)에서 오른쪽 하단으로 이동할 수 있습니다. 코너(m - 1, n - 1).

예 1:

• 입력: 그리드 = [[0,1,1],[1,1,0],[1,1,0]]
• 출력: 2
• 설명: (0, 1)과 (0, 2)의 장애물을 제거하여 (0, 0)에서 (2, 2)까지의 경로를 만들 수 있습니다.
  • 적어도 2개의 장애물을 제거해야 한다는 것을 알 수 있으므로 2개를 반환합니다.
  • 2개의 장애물을 제거하여 경로를 만드는 다른 방법이 있을 수 있습니다.

예 2:

• 입력: 그리드 = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
• 출력: 0
• 설명: 장애물을 제거하지 않고도 (0, 0)에서 (2, 4)로 이동할 수 있으므로 0을 반환합니다.

제약조건:

• m == 그리드.길이
• n == 그리드[i].길이
• 1 5
• 2 5
• 그리드[i][j]는 0 또는 1입니다.
• 그리드[0][0] == 그리드[m - 1][n - 1] == 0

힌트:

1. 셀이 노드이고 가장자리가 인접한 셀 사이에 있는 그래프로 그리드를 모델링합니다. 장애물이 있는 셀에 대한 가장자리의 비용은 1이고 다른 모든 가장자리의 비용은 0입니다.
2. 0-1 너비우선탐색이나 Dijkstra 알고리즘을 사용할 수 있나요?

해결책:

그리드의 각 셀이 노드인 그래프를 사용하여 이 문제를 모델링해야 합니다. 목표는 제거해야 할 장애물 수(1)를 최소화하면서 왼쪽 상단(0, 0)에서 오른쪽 하단(m-1, n-1)으로 이동하는 것입니다.

접근하다:

1. 그래프 표현:

   • 그리드의 각 셀은 노드입니다.
   • 인접한 셀 간의 이동(위, 아래, 왼쪽, 오른쪽)은 가장자리로 처리됩니다.
   • 가장자리가 1(장애물)이 있는 셀을 통과하면 비용은 1(장애물 제거)이고, 0(빈 셀)을 통과하면 비용은 0입니다.

2. 알고리즘 선택:

   • 제거되는 장애물의 수를 최소화해야 하므로 우선순위 큐를 사용하여 0-1 BFS(deque를 사용한 너비 우선 검색) 또는 Dijkstra 알고리즘을 사용할 수 있습니다.
   • 0-1 BFS는 각 모서리의 비용이 0 또는 1이므로 여기에 적합합니다.

3. 0-1 BFS:

   • 우리는 deque(양단 큐)를 사용하여 비용이 다른 노드를 처리합니다.
     • 비용이 0인 셀을 데크 앞으로 밀어넣습니다.
     • 비용이 1인 셀을 데크 뒤로 밀어 넣습니다.
   • 그리드를 탐색하여 항상 장애물 제거가 필요하지 않은 경로를 먼저 확장하고 필요한 경우에만 장애물을 제거하는 것이 아이디어입니다.

이 솔루션을 PHP: 2290으로 구현해 보겠습니다. 코너 도달을 위한 최소 장애물 제거

<?php /**
 * @param Integer[][] $grid
 * @return Integer
 */
function minimumObstacles($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test Case 1
$grid1 = [
    [0, 1, 1],
    [1, 1, 0],
    [1, 1, 0]
];
echo minimumObstacles($grid1) . PHP_EOL; // Output: 2

// Test Case 2
$grid2 = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0]
];
echo minimumObstacles($grid2) . PHP_EOL; // Output: 0
?>

설명:

1. 입력 구문 분석:

   • 그리드를 2차원 배열로 취합니다.
   • 경계 확인을 위해 행과 열이 계산됩니다.

2. Deque 구현:

   • SplDoublyLinkedList는 deque를 시뮬레이션하는 데 사용됩니다. 전면(언시프트) 또는 후면(푸시)에 요소 추가를 지원합니다.

3. 방문한 배열:

   • 중복 처리를 피하기 위해 이미 방문한 셀을 추적합니다.

4. 0-1 BFS 논리:

   • 비용이 0인 (0, 0)부터 시작하세요.
   • 각 인접 셀에 대해:
     • 비어 있는 경우(grid[nx][ny] == 0) 동일한 비용으로 데크 앞에 추가합니다.
     • 장애물(grid[nx][ny] == 1)인 경우 비용이 증가하여 데크 뒷면에 추가하세요.

5. 결과 반환:

   • 오른쪽 하단에 도달하면 비용을 반환합니다.
   • 유효한 경로가 존재하지 않는 경우(문제에서는 경로가 보장되지만) -1을 반환합니다.

---

복잡성:

• 시간 복잡도: O(m x n), 여기서 m은 행 수이고 n은 열 수입니다. 각 셀은 한 번씩 처리됩니다.
• 공간 복잡도: O(m x n), 방문 배열 및 데크의 경우

이 구현은 주어진 제약 내에서 효율적으로 작동합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 코너 도달을 위한 최소 장애물 제거의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!