694. Number of Distinct Islands (Hash Table, Depth-First Search, Breadth-First Search, Union Find, Hash Function)

링크 - https://leetcode.com/problems/number-of-distinct-islands/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Medium

Intuition

우리는 이문제를 DFS와 pattern을 사용해서 풀 수 있다. 먼저 각 row와 col로 이동할때 pattern을 더해주고, dfs가 끝날때 "0"을 더해줌으로써 unique한 pattern을 가져갈수 있다. 

list를 set에 더해줄때는 꼭 tuple()을 사용하는것을 잊지 말자.

Code

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        def dfs(row, col, pattern):
            if row < 0 or col < 0 or row >= rows or col >= cols:
                return
            if grid[row][col] == 0 or (row, col) in visited:
                return

            visited.add((row, col))
            cur_pattern.append(pattern)
            dfs(row-1, col, "U")
            dfs(row+1, col, "D")
            dfs(row, col+1, "R")
            dfs(row, col-1, "L")
            cur_pattern.append("0")


        visited = set()
        unique_patterns = set()
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1 and (row, col) not in visited:
                    cur_pattern = []
                    dfs(row, col, "0")
                    if cur_pattern:
                        unique_patterns.add(tuple(cur_pattern))

        return len(unique_patterns)

Complexity

Time Complexity: O(M*N)

Space Complexity: O(M*N)