. 동일한 행이나 열에서 제거된 대부분의 돌

947. 같은 행이나 열에서 가장 많이 제거된 돌

난이도:중

주제: 해시 테이블, 깊이 우선 검색, Union Find, 그래프

2D 평면에서는 정수 좌표점에 n개의 돌을 배치합니다. 각 좌표점에는 최대 1개의 돌이 있을 수 있습니다.

스톤은 제거되지 않은 다른 스톤과 같은 행이나 같은 열을 공유하는 경우 제거될 수 있습니다.

stone[i] = [xi, yi]가 i^번째 돌의 위치를 ​​나타내는 n 길이의 돌 배열이 있는 경우 제거할 수 있는 가능한 가장 큰 돌 수를 반환합니다. .

예 1:

• 입력: 돌 = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
• 출력: 5
• 설명: 돌 5개를 제거하는 방법 중 하나는 다음과 같습니다.
  1. 스톤 [2,2]는 [2,1]과 같은 행을 공유하므로 제거하세요.
  2. 스톤 [2,1]은 [0,1]과 동일한 열을 공유하므로 제거하세요.
  3. 스톤 [1,2]는 [1,0]과 같은 행을 공유하므로 제거하세요.
  4. 스톤 [1,0]은 [0,0]과 동일한 열을 공유하므로 제거하세요.
  5. 스톤 [0,1]은 [0,0]과 같은 행을 공유하므로 제거하세요.
  6. 스톤 [0,0]은 평면에 있는 다른 스톤과 행/열을 공유하지 않으므로 제거할 수 없습니다.

예 2:

• 입력: 돌 = [[0,0],[0,2],[1,1],[2,0],[2,2]]
• 출력: 3
• 설명: 3개 동작을 수행하는 한 가지 방법은 다음과 같습니다.
  1. 스톤 [2,2]는 [2,0]과 같은 행을 공유하므로 제거하세요.
  2. 스톤 [2,0]은 [0,0]과 동일한 열을 공유하므로 제거하세요.
  3. 스톤 [0,2]는 [0,0]과 같은 행을 공유하므로 제거하세요.
  4. 스톤 [0,0] 및 [1,1]은 평면에 있는 다른 스톤과 행/열을 공유하지 않으므로 제거할 수 없습니다.

예 3:

• 입력: 돌 = [[0,0]]
• 출력: 0
• 설명: [0,0]은 비행기에 있는 유일한 돌이므로 제거할 수 없습니다.

제약조건:

• 1
• 0 i, y_i 4
• 두 개의 돌이 같은 좌표에 있을 수 없습니다.

해결책:

DFS(깊이 우선 검색) 접근 방식을 사용하여 솔루션을 구현할 수 있습니다. 행이나 열로 연결된 돌을 동일한 연결된 구성 요소의 일부로 간주하는 것이 아이디어입니다. 연결된 부품을 모두 찾았을 때, 제거할 수 있는 최대 돌 개수는 총 돌 개수에서 연결된 부품 개수를 뺀 값입니다.

이 솔루션을 PHP로 구현해 보겠습니다: 947. 같은 행이나 열에서 가장 많은 돌이 제거됨

<?php function removeStones($stones) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

function dfs($stoneIndex, &$stones, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$stones1 = array(
    array(0, 0),
    array(0, 1),
    array(1, 0),
    array(1, 2),
    array(2, 1),
    array(2, 2)
);
echo removeStones($stones1); // Output: 5

$stones2 = array(
    array(0, 0),
    array(0, 2),
    array(1, 1),
    array(2, 0),
    array(2, 2)
);
echo removeStones($stones2); // Output: 3

$stones3 = array(
    array(0, 0)
);
echo removeStones($stones3); // Output: 0
?>

설명:

1. DFS 기능:

   • dfs 함수는 동일한 연결된 구성 요소에 있는 모든 돌을 탐색하는 데 사용됩니다. 현재 스톤에 스톤이 (같은 행이나 열에) 연결되어 있으면 해당 스톤에 대해 재귀적으로 DFS를 수행합니다.

2. 주요 기능:

   • 우리는 모든 돌에 대해 반복하고 방문하지 않은 각 돌에 대해 DFS를 수행하여 동일한 연결된 구성 요소에 있는 모든 돌을 표시합니다.
   • 연결된 구성 요소 수를 세고 결과는 총 돌 수에서 연결된 구성 요소 수($n - $numComponents)를 뺀 값입니다.

3. 실행 예:

   • 첫 번째 예에서는 제거할 수 있는 돌 5개를 정확하게 찾아냈고, 제거할 수 없는 돌 1개는 남았습니다.

복잡성:

• 시간 복잡도: 중첩 루프 및 DFS 순회로 인해 O(n^2)
• 공간 복잡도: 방문한 돌을 저장하는 O(n)

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

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 . 동일한 행이나 열에서 제거된 대부분의 돌의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!