섬 연결을 끊는 데 필요한 최소 일수

1568. 섬 연결을 끊는 최소 일수

난이도:어려움

주제: 배열, 깊이 우선 검색, 너비 우선 검색, 행렬, 강한 연결 구성 요소

1은 땅을 나타내고 0은 물을 나타내는 m x n 이진 격자 격자가 제공됩니다. 섬은 1이 최대 4방향(수평 또는 수직)으로 연결된 그룹입니다.

그리드가 정확히 하나의 섬인 경우 연결됨이라고 하고, 그렇지 않은 경우 연결 해제합니다.

어느 날, 우리는 **모든 단일 육지 세포(1)를 물 세포(0)로 바꿀 수 있습니다.

전력망 연결을 끊는 데 필요한 최소 일수를 반환합니다.

예 1:

• 입력: 그리드 = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
• 출력: 2
• 설명: 연결이 끊긴 그리드를 얻으려면 최소 2일이 필요합니다. 육지 그리드[1][1] 및 그리드[0][2]를 물로 변경하고 연결되지 않은 섬 2개를 얻습니다.

예 2:

• 입력: 그리드 = [[1,1]]
• 출력: 2
• 설명: 가득 찬 물의 그리드도 연결이 끊어졌습니다([[1,1]] -> [[0,0]]), 0개의 섬

제약조건:

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

힌트:

1. 그리드가 이미 연결 해제된 경우 0을 반환합니다.
2. 단일 토지를 물로 변경하는 경우 1을 반환하여 섬 연결을 끊습니다.
3. 그렇지 않으면 2를 반환합니다.
4. 최대 2일 이내에 전력망 연결을 끊을 수 있습니다.

해결책:

다음 단계를 고려해야 합니다.

문제 해결 단계:

1. 초기 연결 확인: 먼저 그리드에 아일랜드가 두 개 이상 있는지 확인하여 그리드가 이미 연결 해제되었는지 확인합니다. 이미 연결이 끊어진 경우 0을 반환합니다.

2. 단일 제거로 인해 섬이 분리되는지 확인: 그리드의 각 셀을 반복합니다. 셀을 1에서 0(1인 경우)으로 임시 변환하고, 아일랜드 개수를 세어 그리드가 끊어지는지 확인합니다. 단일 셀을 변환하면 섬의 연결이 끊어지면 1을 반환합니다.

3. 이틀 간의 연결 끊김: 단일 셀 변환이 섬의 연결을 끊지 않으면 인접한 두 개의 육지 셀을 변환하여 그리드의 연결을 끊을 수 있습니다. 따라서 2를 반환합니다.

주요 기능:

• DFS(깊이 우선 검색) 섬을 찾고 개수를 계산합니다.
• isConnected 그리드가 연결되어 있는지 확인하세요.

PHP에서 이 솔루션을 구현해 보겠습니다: 1568. 섬 연결을 끊는 최소 일수

<?php
// Example usage:
$grid1 = [
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
];
echo minDays($grid1); // Output: 2

$grid2 = [
    [1, 1]
];
echo minDays($grid2); // Output: 2
?>

설명:

• minDays() 함수는 메인 로직을 처리합니다.
• countIslands()는 DFS를 사용하여 존재하는 섬의 수를 계산합니다.
• dfs()는 그리드를 탐색하고 방문한 육지 셀을 표시하는 재귀 함수입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 섬 연결을 끊는 데 필요한 최소 일수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!