코너 도달을 위한 최소 장애물 제거
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으로 구현해 보겠습니다. 코너 도달을 위한 최소 장애물 제거
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
설명:
-
입력 구문 분석:
- 그리드를 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에는 4 가지 주요 오류 유형이 있습니다. 1. NOTICE : 가장 작은 것은 정의되지 않은 변수에 액세스하는 것과 같이 프로그램을 방해하지 않습니다. 2. 경고 : 심각한 통지는 파일을 포함하지 않는 것과 같은 프로그램을 종료하지 않습니다. 3. FatalError : 가장 심각한 것은 기능을 부르는 것과 같은 프로그램을 종료합니다. 4. parseerror : 구문 오류는 엔드 태그를 추가하는 것을 잊어 버리는 것과 같이 프로그램이 실행되는 것을 방지합니다.

PHP와 Python은 각각 고유 한 장점이 있으며 프로젝트 요구 사항에 따라 선택합니다. 1.PHP는 웹 개발, 특히 웹 사이트의 빠른 개발 및 유지 보수에 적합합니다. 2. Python은 간결한 구문을 가진 데이터 과학, 기계 학습 및 인공 지능에 적합하며 초보자에게 적합합니다.

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

PHP는 전자 상거래, 컨텐츠 관리 시스템 및 API 개발에 널리 사용됩니다. 1) 전자 상거래 : 쇼핑 카트 기능 및 지불 처리에 사용됩니다. 2) 컨텐츠 관리 시스템 : 동적 컨텐츠 생성 및 사용자 관리에 사용됩니다. 3) API 개발 : 편안한 API 개발 및 API 보안에 사용됩니다. 성능 최적화 및 모범 사례를 통해 PHP 애플리케이션의 효율성과 유지 보수 성이 향상됩니다.

HTTP 요청 방법에는 각각 리소스를 확보, 제출, 업데이트 및 삭제하는 데 사용되는 Get, Post, Put and Delete가 포함됩니다. 1. GET 방법은 리소스를 얻는 데 사용되며 읽기 작업에 적합합니다. 2. 게시물은 데이터를 제출하는 데 사용되며 종종 새로운 리소스를 만드는 데 사용됩니다. 3. PUT 방법은 리소스를 업데이트하는 데 사용되며 완전한 업데이트에 적합합니다. 4. 삭제 방법은 자원을 삭제하는 데 사용되며 삭제 작업에 적합합니다.

PHP는 서버 측에서 널리 사용되는 스크립팅 언어이며 특히 웹 개발에 적합합니다. 1.PHP는 HTML을 포함하고 HTTP 요청 및 응답을 처리 할 수 있으며 다양한 데이터베이스를 지원할 수 있습니다. 2.PHP는 강력한 커뮤니티 지원 및 오픈 소스 리소스를 통해 동적 웹 컨텐츠, 프로세스 양식 데이터, 액세스 데이터베이스 등을 생성하는 데 사용됩니다. 3. PHP는 해석 된 언어이며, 실행 프로세스에는 어휘 분석, 문법 분석, 편집 및 실행이 포함됩니다. 4. PHP는 사용자 등록 시스템과 같은 고급 응용 프로그램을 위해 MySQL과 결합 할 수 있습니다. 5. PHP를 디버깅 할 때 error_reporting () 및 var_dump ()와 같은 함수를 사용할 수 있습니다. 6. 캐싱 메커니즘을 사용하여 PHP 코드를 최적화하고 데이터베이스 쿼리를 최적화하며 내장 기능을 사용하십시오. 7

PHP는 $ \ _ 파일 변수를 통해 파일 업로드를 처리합니다. 보안을 보장하는 방법에는 다음이 포함됩니다. 1. 오류 확인 확인, 2. 파일 유형 및 크기 확인, 3 파일 덮어 쓰기 방지, 4. 파일을 영구 저장소 위치로 이동하십시오.

phpoop에서 self ::는 현재 클래스를 말하며, Parent ::는 부모 클래스를 말하며, static ::는 늦은 static 바인딩에 사용됩니다. 1. self :: 정적 방법과 일정한 호출에 사용되지만 늦은 정적 바인딩을 지원하지는 않습니다. 2.parent :: 하위 클래스가 상위 클래스 방법을 호출하는 데 사용되며 개인 방법에 액세스 할 수 없습니다. 3. Static ::는 상속 및 다형성에 적합한 후기 정적 결합을 지원하지만 코드의 가독성에 영향을 줄 수 있습니다.
