. 동일한 행이나 열에서 제거된 대부분의 돌-PHP 튜토리얼-php.cn

. Most Stones Removed with Same Row or Column

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_i4
두 개의 돌이 같은 좌표에 있을 수 없습니다.

해결책:

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

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

으아아아

설명:

DFS 기능:
- dfs 함수는 동일한 연결된 구성 요소에 있는 모든 돌을 탐색하는 데 사용됩니다. 현재 스톤에 스톤이 (같은 행이나 열에) 연결되어 있으면 해당 스톤에 대해 재귀적으로 DFS를 수행합니다.
주요 기능:
- 우리는 모든 돌에 대해 반복하고 방문하지 않은 각 돌에 대해 DFS를 수행하여 동일한 연결된 구성 요소에 있는 모든 돌을 표시합니다.
- 연결된 구성 요소 수를 세고 결과는 총 돌 수에서 연결된 구성 요소 수($n - $numComponents)를 뺀 값입니다.
실행 예:
- 첫 번째 예에서는 제거할 수 있는 돌 5개를 정확하게 찾아냈고, 제거할 수 없는 돌 1개는 남았습니다.