Leetcode7

from collections import deque

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        
        q = deque()
        dy, dx = [1,-1,0,0], [0,0,1,-1]
        n, m = len(board), len(board[0])
        
        for i in range(n):
            for j in range(m):
                if board[i][j] == word[0]:
                    visited_set = set()
                    visited_set.add((i, j))
                    q.append([i,j,visited_set])
        
        if len(q) == 0: # we can't start
            return False
        
        if len(word) == 1: # do not have to check word
            return True

        while q:
            y, x, visited_set = q.popleft()

            for i in range(4):
                ny, nx = y+dy[i], x+dx[i]
                if (0 <= ny < n and 0 <= nx < m) and (ny, nx) not in visited_set and board[ny][nx] == word[len(visited_set)]:
                    if len(visited_set)+1 == len(word):
                        return True
                    next_visited_set = visited_set.copy()
                    next_visited_set.add((ny, nx))
                    q.append([ny, nx, next_visited_set])
        
        return False

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.word = None
        
class Solution(object):
    def findWords(self, board, words):
        # Trie 구축
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.isWord = True
            node.word = word
            
        rows, cols = len(board), len(board[0])
        result = set()
        
        def dfs(row, col, node):
            # 현재 위치의 문자 저장
            char = board[row][col]
            curr = node.children.get(char)
            
            # 현재 노드가 없으면 반환
            if not curr:
                return
            
            # 단어를 찾았다면 결과에 추가
            if curr.isWord:
                result.add(curr.word)
                
            # 현재 셀 방문 표시
            board[row][col] = '#'
            
            # 4방향 탐색
            for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
                new_row, new_col = row + dx, col + dy
                if 0 <= new_row < rows and 0 <= new_col < cols and board[new_row][new_col] != '#':
                    dfs(new_row, new_col, curr)
                    
            # 방문 표시 복원
            board[row][col] = char
        
        # 보드의 모든 위치에서 DFS 시작
        for i in range(rows):
            for j in range(cols):
                dfs(i, j, root)
                
        return list(result)