백엔드 개발 PHP 튜토리얼 코너 도달을 위한 최소 장애물 제거

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

Dec 01, 2024 am 10:39 AM

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

난이도:어려움

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

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

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

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

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

예 1:

Minimum Obstacle Removal to Reach Corner

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

예 2:

Minimum Obstacle Removal to Reach Corner

  • 입력: 그리드 = [[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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

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

인기 기사

<gum> : Bubble Gum Simulator Infinity- 로얄 키를 얻고 사용하는 방법
4 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
Nordhold : Fusion System, 설명
4 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora : 마녀 트리의 속삭임 - Grappling Hook 잠금 해제 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

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

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

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

PHP에서 보안 비밀번호 해싱을 설명하십시오 (예 : Password_hash, Password_Verify). 왜 MD5 또는 SHA1을 사용하지 않습니까? PHP에서 보안 비밀번호 해싱을 설명하십시오 (예 : Password_hash, Password_Verify). 왜 MD5 또는 SHA1을 사용하지 않습니까? Apr 17, 2025 am 12:06 AM

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

스칼라 유형, 반환 유형, 노조 유형 및 무효 유형을 포함한 PHP 유형의 힌트 작업은 어떻게 작동합니까? 스칼라 유형, 반환 유형, 노조 유형 및 무효 유형을 포함한 PHP 유형의 힌트 작업은 어떻게 작동합니까? Apr 17, 2025 am 12:25 AM

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

PHP와 Python : 다른 패러다임이 설명되었습니다 PHP와 Python : 다른 패러다임이 설명되었습니다 Apr 18, 2025 am 12:26 AM

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

PHP 및 Python : 코드 예제 및 비교 PHP 및 Python : 코드 예제 및 비교 Apr 15, 2025 am 12:07 AM

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

PHP에서 SQL 주입을 어떻게 방지합니까? (준비된 진술, pdo) PHP에서 SQL 주입을 어떻게 방지합니까? (준비된 진술, pdo) Apr 15, 2025 am 12:15 AM

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

PHP : 데이터베이스 및 서버 측 로직 처리 PHP : 데이터베이스 및 서버 측 로직 처리 Apr 15, 2025 am 12:15 AM

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

PHP의 목적 : 동적 웹 사이트 구축 PHP의 목적 : 동적 웹 사이트 구축 Apr 15, 2025 am 12:18 AM

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

PHP와 Python 중에서 선택 : 가이드 PHP와 Python 중에서 선택 : 가이드 Apr 18, 2025 am 12:24 AM

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

See all articles