코너 도달을 위한 최소 장애물 제거
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이고 다른 모든 가장자리의 비용은 0입니다.
- 0-1 너비우선탐색이나 Dijkstra 알고리즘을 사용할 수 있나요?
해결책:
그리드의 각 셀이 노드인 그래프를 사용하여 이 문제를 모델링해야 합니다. 목표는 제거해야 할 장애물 수(1)를 최소화하면서 왼쪽 상단(0, 0)에서 오른쪽 하단(m-1, n-1)으로 이동하는 것입니다.
접근하다:
-
그래프 표현:
- 그리드의 각 셀은 노드입니다.
- 인접한 셀 간의 이동(위, 아래, 왼쪽, 오른쪽)은 가장자리로 처리됩니다.
- 가장자리가 1(장애물)이 있는 셀을 통과하면 비용은 1(장애물 제거)이고, 0(빈 셀)을 통과하면 비용은 0입니다.
-
알고리즘 선택:
- 제거되는 장애물의 수를 최소화해야 하므로 우선순위 큐를 사용하여 0-1 BFS(deque를 사용한 너비 우선 검색) 또는 Dijkstra 알고리즘을 사용할 수 있습니다.
- 0-1 BFS는 각 모서리의 비용이 0 또는 1이므로 여기에 적합합니다.
-
0-1 BFS:
- 우리는 deque(양단 큐)를 사용하여 비용이 다른 노드를 처리합니다.
- 비용이 0인 셀을 데크 앞으로 밀어넣습니다.
- 비용이 1인 셀을 데크 뒤로 밀어 넣습니다.
- 그리드를 탐색하여 항상 장애물 제거가 필요하지 않은 경로를 먼저 확장하고 필요한 경우에만 장애물을 제거하는 것이 아이디어입니다.
- 우리는 deque(양단 큐)를 사용하여 비용이 다른 노드를 처리합니다.
이 솔루션을 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 ?>
설명:
-
입력 구문 분석:
- 그리드를 2차원 배열로 취합니다.
- 경계 확인을 위해 행과 열이 계산됩니다.
-
Deque 구현:
- SplDoublyLinkedList는 deque를 시뮬레이션하는 데 사용됩니다. 전면(언시프트) 또는 후면(푸시)에 요소 추가를 지원합니다.
-
방문한 배열:
- 중복 처리를 피하기 위해 이미 방문한 셀을 추적합니다.
-
0-1 BFS 논리:
- 비용이 0인 (0, 0)부터 시작하세요.
- 각 인접 셀에 대해:
- 비어 있는 경우(grid[nx][ny] == 0) 동일한 비용으로 데크 앞에 추가합니다.
- 장애물(grid[nx][ny] == 1)인 경우 비용이 증가하여 데크 뒷면에 추가하세요.
-
결과 반환:
- 오른쪽 하단에 도달하면 비용을 반환합니다.
- 유효한 경로가 존재하지 않는 경우(문제에서는 경로가 보장되지만) -1을 반환합니다.
복잡성:
- 시간 복잡도: O(m x n), 여기서 m은 행 수이고 n은 열 수입니다. 각 셀은 한 번씩 처리됩니다.
- 공간 복잡도: O(m x n), 방문 배열 및 데크의 경우
이 구현은 주어진 제약 내에서 효율적으로 작동합니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
- 링크드인
- 깃허브
위 내용은 코너 도달을 위한 최소 장애물 제거의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

Video Face Swap
완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

PHP에서 Password_hash 및 Password_Verify 기능을 사용하여 보안 비밀번호 해싱을 구현해야하며 MD5 또는 SHA1을 사용해서는 안됩니다. 1) Password_hash는 보안을 향상시키기 위해 소금 값이 포함 된 해시를 생성합니다. 2) Password_verify 암호를 확인하고 해시 값을 비교하여 보안을 보장합니다. 3) MD5 및 SHA1은 취약하고 소금 값이 부족하며 현대 암호 보안에는 적합하지 않습니다.

PHP 유형은 코드 품질과 가독성을 향상시키기위한 프롬프트입니다. 1) 스칼라 유형 팁 : PHP7.0이므로 int, float 등과 같은 기능 매개 변수에 기본 데이터 유형을 지정할 수 있습니다. 2) 반환 유형 프롬프트 : 기능 반환 값 유형의 일관성을 확인하십시오. 3) Union 유형 프롬프트 : PHP8.0이므로 기능 매개 변수 또는 반환 값에 여러 유형을 지정할 수 있습니다. 4) Nullable 유형 프롬프트 : NULL 값을 포함하고 널 값을 반환 할 수있는 기능을 포함 할 수 있습니다.

PHP는 주로 절차 적 프로그래밍이지만 객체 지향 프로그래밍 (OOP)도 지원합니다. Python은 OOP, 기능 및 절차 프로그래밍을 포함한 다양한 패러다임을 지원합니다. PHP는 웹 개발에 적합하며 Python은 데이터 분석 및 기계 학습과 같은 다양한 응용 프로그램에 적합합니다.

PHP와 Python은 고유 한 장점과 단점이 있으며 선택은 프로젝트 요구와 개인 선호도에 달려 있습니다. 1.PHP는 대규모 웹 애플리케이션의 빠른 개발 및 유지 보수에 적합합니다. 2. Python은 데이터 과학 및 기계 학습 분야를 지배합니다.

PHP에서 전처리 문과 PDO를 사용하면 SQL 주입 공격을 효과적으로 방지 할 수 있습니다. 1) PDO를 사용하여 데이터베이스에 연결하고 오류 모드를 설정하십시오. 2) 준비 방법을 통해 전처리 명세서를 작성하고 자리 표시자를 사용하여 데이터를 전달하고 방법을 실행하십시오. 3) 쿼리 결과를 처리하고 코드의 보안 및 성능을 보장합니다.

PHP는 MySQLI 및 PDO 확장 기능을 사용하여 데이터베이스 작업 및 서버 측 로직 프로세싱에서 상호 작용하고 세션 관리와 같은 기능을 통해 서버 측로 로직을 처리합니다. 1) MySQLI 또는 PDO를 사용하여 데이터베이스에 연결하고 SQL 쿼리를 실행하십시오. 2) 세션 관리 및 기타 기능을 통해 HTTP 요청 및 사용자 상태를 처리합니다. 3) 트랜잭션을 사용하여 데이터베이스 작업의 원자력을 보장하십시오. 4) SQL 주입 방지, 디버깅을 위해 예외 처리 및 폐쇄 연결을 사용하십시오. 5) 인덱싱 및 캐시를 통해 성능을 최적화하고, 읽을 수있는 코드를 작성하고, 오류 처리를 수행하십시오.

PHP는 동적 웹 사이트를 구축하는 데 사용되며 해당 핵심 기능에는 다음이 포함됩니다. 1. 데이터베이스와 연결하여 동적 컨텐츠를 생성하고 웹 페이지를 실시간으로 생성합니다. 2. 사용자 상호 작용 및 양식 제출을 처리하고 입력을 확인하고 작업에 응답합니다. 3. 개인화 된 경험을 제공하기 위해 세션 및 사용자 인증을 관리합니다. 4. 성능을 최적화하고 모범 사례를 따라 웹 사이트 효율성 및 보안을 개선하십시오.

PHP는 웹 개발 및 빠른 프로토 타이핑에 적합하며 Python은 데이터 과학 및 기계 학습에 적합합니다. 1.PHP는 간단한 구문과 함께 동적 웹 개발에 사용되며 빠른 개발에 적합합니다. 2. Python은 간결한 구문을 가지고 있으며 여러 분야에 적합하며 강력한 라이브러리 생태계가 있습니다.
