![. Most Stones Removed with Same Row or Column](https://img.php.cn/upload/article/000/000/000/172497106529050.jpg)
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개를 제거하는 방법 중 하나는 다음과 같습니다.
- 스톤 [2,2]는 [2,1]과 같은 행을 공유하므로 제거하세요.
- 스톤 [2,1]은 [0,1]과 동일한 열을 공유하므로 제거하세요.
- 스톤 [1,2]는 [1,0]과 같은 행을 공유하므로 제거하세요.
- 스톤 [1,0]은 [0,0]과 동일한 열을 공유하므로 제거하세요.
- 스톤 [0,1]은 [0,0]과 같은 행을 공유하므로 제거하세요.
- 스톤 [0,0]은 평면에 있는 다른 스톤과 행/열을 공유하지 않으므로 제거할 수 없습니다.
예 2:
- 입력:돌 = [[0,0],[0,2],[1,1],[2,0],[2,2]]
- 출력:3
- 설명:3개 동작을 수행하는 한 가지 방법은 다음과 같습니다.
- 스톤 [2,2]는 [2,0]과 같은 행을 공유하므로 제거하세요.
- 스톤 [2,0]은 [0,0]과 동일한 열을 공유하므로 제거하세요.
- 스톤 [0,2]는 [0,0]과 같은 행을 공유하므로 제거하세요.
- 스톤 [0,0] 및 [1,1]은 평면에 있는 다른 스톤과 행/열을 공유하지 않으므로 제거할 수 없습니다.
예 3:
- 입력:돌 = [[0,0]]
- 출력:0
- 설명:[0,0]은 비행기에 있는 유일한 돌이므로 제거할 수 없습니다.
제약조건:
- 1
- 0 i, yi4
- 두 개의 돌이 같은 좌표에 있을 수 없습니다.
해결책:
DFS(깊이 우선 검색) 접근 방식을 사용하여 솔루션을 구현할 수 있습니다. 행이나 열로 연결된 돌을 동일한 연결된 구성 요소의 일부로 간주하는 것이 아이디어입니다. 연결된 부품을 모두 찾았을 때, 제거할 수 있는 최대 돌 개수는 총 돌 개수에서 연결된 부품 개수를 뺀 값입니다.
이 솔루션을 PHP로 구현해 보겠습니다:947. 같은 행이나 열에서 가장 많은 돌이 제거됨
으아아아
설명:
DFS 기능:
- dfs 함수는 동일한 연결된 구성 요소에 있는 모든 돌을 탐색하는 데 사용됩니다. 현재 스톤에 스톤이 (같은 행이나 열에) 연결되어 있으면 해당 스톤에 대해 재귀적으로 DFS를 수행합니다.
주요 기능:
- 우리는 모든 돌에 대해 반복하고 방문하지 않은 각 돌에 대해 DFS를 수행하여 동일한 연결된 구성 요소에 있는 모든 돌을 표시합니다.
- 연결된 구성 요소 수를 세고 결과는 총 돌 수에서 연결된 구성 요소 수($n - $numComponents)를 뺀 값입니다.
실행 예:
- 첫 번째 예에서는 제거할 수 있는 돌 5개를 정확하게 찾아냈고, 제거할 수 없는 돌 1개는 남았습니다.
복잡성:
- 시간 복잡도: 중첩 루프 및 DFS 순회로 인해 O(n^2).
- 공간 복잡도: 방문한 돌을 저장하는 O(n)
이 솔루션은 주어진 제약 내에서 효율적으로 작동해야 합니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
위 내용은 . 동일한 행이나 열에서 제거된 대부분의 돌의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!