[LeetCode] 947 | Most Stones Removed with Same Row or Column | Python

---

문제 링크: https://leetcode.com/problems/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.

---

조건

• 1 <= stones.length <= 1000
• 0 <= $x_i, y_i$ <= $10^4$
• No two stones are at the same coordinate point.

---

내 풀이

같은 행이나 열에 있는 돌들의 뜻은 코딩테스트에 종종 나오는 islands(섬)의 개념이 된다.

아래 그림처럼 섬 하나에 대해서는 돌을 하나만 남기고 다 지울 수 있게 된다.

따라서 지울 수 있는 돌의 갯수는, [전체 돌의 수 - 섬의 수]가 된다.

---

코드

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        def dfs(x, y):
            to_visit.remove((x, y))
            
            for j in rows[x]:
                if (x, j) in to_visit:
                    dfs(x, j)
            for i in cols[y]:
                if (i, y) in to_visit:
                    dfs(i, y)
        
        to_visit = {(i, j) for i, j in stones}
        islands = 0
        rows, cols = defaultdict(list), defaultdict(list)
        
        for x, y in stones:
            rows[x].append(y)
            cols[y].append(x)
        
        for x, y in stones:
            if (x, y) in to_visit:
                dfs(x, y)
                islands += 1
        
        return len(stones) - islands