하위 섬 수

1905. 하위섬 백작

난이도:중

주제: 배열, 깊이 우선 검색, 너비 우선 검색, 결합 찾기, 행렬

0(물을 나타냄)과 1(땅을 나타냄)만 포함하는 두 개의 m x n 이진 행렬 Grid1과 Grid2가 제공됩니다. 섬은 4방향(수평 또는 수직)으로 연결된 1개의 그룹입니다. 그리드 외부의 모든 셀은 물 셀로 간주됩니다.

grid2의 이 섬을 구성하는 셀을 모두 포함하는 Grid1의 섬이 있는 경우 Grid2의 섬은 하위 섬으로 간주됩니다. .

하위 섬으로 간주되는 Grid2의 섬 개 를 반환합니다.

예 1:

• 입력: 그리드1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1, 0,0,0,0],[1,1,0,1,1]], 그리드2 = [[1,1,1,0,0],[0,0,1,1,1],[ 0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
• 출력: 3
• 설명:
  • 위 사진에서 왼쪽 그리드가 그리드1, 오른쪽 그리드가 그리드2입니다.
  • 그리드2에서 빨간색으로 표시된 1은 하위 섬의 일부로 간주되는 것입니다. 세 개의 하위 섬이 있습니다.

예 2:

• 입력: 그리드1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1, 1,1,1,1],[1,0,1,0,1]], 그리드2 = [[0,0,0,0,0],[1,1,1,1,1],[ 0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
• 출력: 2
• 설명:
  • 위 사진에서 왼쪽 그리드가 그리드1, 오른쪽 그리드가 그리드2입니다.
  • 그리드2에서 빨간색으로 표시된 1은 하위 섬의 일부로 간주되는 것입니다. 두 개의 하위 섬이 있습니다.

제약조건:

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

힌트:

1. Floodfill을 사용하여 두 번째 그리드의 섬을 반복해 보겠습니다
2. 두 번째 그리드의 섬에 있는 모든 셀이 첫 번째 그리드의 육지로 표현되면 서로 연결되어 해당 섬을 하위 섬으로 만듭니다.

해결책:

DFS(깊이 우선 검색) 접근 방식을 사용하여 그리드 2의 섬을 탐색하고 각 섬이 그리드 1의 해당 섬 내에 완전히 포함되어 있는지 확인합니다. 솔루션을 구현하는 방법은 다음과 같습니다.

단계:

1. 그리드 탐색: 그리드 2의 각 셀을 반복합니다.
2. 그리드2에서 섬 식별: 그리드2에서 육지 셀(1)을 만나면 DFS를 사용하여 섬 전체를 탐색합니다.
3. 하위 섬 조건 확인: Grid2의 섬에서 DFS를 수행하는 동안 Grid1의 해당 셀이 모두 육상 셀인지 확인합니다. 그렇다면 그 섬은 부섬이다.
4. 하위 섬 개수: 하위 섬 조건을 충족하는 Grid2의 각 섬에 대해 하위 섬 개수를 늘립니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1905. 서브섬 백작

<?php
/**
 * @param $grid1
 * @param $grid2
 * @return int
 */
function countSubIslands($grid1, $grid2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $grid1
 * @param $grid2
 * @param $i
 * @param $j
 * @param $m
 * @param $n
 * @return int|true
 */
function dfs(&$grid1, &$grid2, $i, $j, $m, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1
$grid1 = [
    [1,1,1,0,0],
    [0,1,1,1,1],
    [0,0,0,0,0],
    [1,0,0,0,0],
    [1,1,0,1,1]
];

$grid2 = [
    [1,1,1,0,0],
    [0,0,1,1,1],
    [0,1,0,0,0],
    [1,0,1,1,0],
    [0,1,0,1,0]
];

echo countSubIslands($grid1, $grid2); // Output: 3

// Example 2
$grid1 = [
    [1,0,1,0,1],
    [1,1,1,1,1],
    [0,0,0,0,0],
    [1,1,1,1,1],
    [1,0,1,0,1]
];

$grid2 = [
    [0,0,0,0,0],
    [1,1,1,1,1],
    [0,1,0,1,0],
    [0,1,0,1,0],
    [1,0,0,0,1]
];

echo countSubIslands($grid1, $grid2); // Output: 2
?>

설명:

• DFS 함수: dfs 함수는 그리드2의 섬을 탐색하고 그리드1의 해당 셀이 모두 육지 셀인지 확인합니다. 그리드2의 셀 중 하나가 육지이고 그리드1의 해당 셀이 물인 경우 그리드2의 섬은 하위 섬이 아닙니다.
• 방문한 표시: Grid2를 탐색하면서 셀을 0으로 설정하여 방문한 셀로 표시합니다.
• 메인 루프: 그리드2의 모든 셀을 반복합니다. 방문하지 않은 육지 셀을 발견할 때마다 DFS를 시작하여 하위 섬의 일부인지 확인합니다.

시간 복잡도:

시간 복잡도는 (O(m x n))입니다. 여기서 m은 행 수이고 n은 열 수입니다. 이는 잠재적으로 모든 셀을 한 번씩 방문할 수 있기 때문입니다.

이 솔루션은 주어진 제약 내에서 효율적으로 작동해야 합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 하위 섬 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!