Leetcode 947. Most Stones Removed with Same Row or Column

문제

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.

• 2D 공간에 위치한 돌이 자신과 동일한 행 혹은 열에 다른 돌이 하나라도 있으면 제거 가능하다.
• 제거 가능한 최대한의 돌의 갯수를 구하시오

예시

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

총 5개 제거가 가능하다.

제한

• $1 <= stones.length <= 1000$
• $0 <= x_i, y_i <= 10^4$

풀이

• 제거 가능한 모든 돌은 곧, 전체 돌의 갯수에서 제거해선 안되는 모든 돌의 수와 같다.
• 한 돌에서 시작해 이 돌과 같은 행/열 을 가지는 모든 돌들을 재귀적으로 찾아나가서 체크해준다.

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        
        rows = {}
        cols = {}
        
        for row, col in stones:
            if row not in rows:
                rows[row] = []
            if col not in cols:
                cols[col] = []
            rows[row].append((row, col))
            cols[col].append((row, col))
            
        visited = set()
            
        def dfs(row, col):
            if (row, col) not in visited:
                visited.add((row, col))
                for r, c in rows[row]:
                    dfs(r, c)
                for r, c in cols[col]:
                    dfs(r, c)
                    
        count = 0
        
        for row, col in stones:
            if (row, col) not in visited:
                dfs(row, col)
                count += 1
                
        return len(stones) - count