Backtracking: 79. Word Search

79. Word Search

 

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        visit = set()

        def backtrack(r, c, index):
            # 단어의 모든 문자를 찾았을 경우 True 반환
            if index == len(word):
                return True

            # 현재 위치가 유효하지 않거나, 
            # 이미 방문했거나, 
            # 문자가 일치하지 않을 경우 False 반환
            if (r < 0 or r >= ROWS or c < 0 or c >= COLS or 
                (r, c) in visit or board[r][c] != word[index]):
                return False

            # 현재 좌표 방문 표시
            visit.add((r, c))

            for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                if backtrack(r+dr, c+dc, index+1):
                    return True
                
            # 방문 표시 제거
            visit.remove((r, c))
            return False

        # 모든 셀에서 탐색 시작
        for r in range(ROWS):
            for c in range(COLS):
                # 첫째 단어에서 시작해서, True 반환 받은 경우만, True 반환 
                if board[r][c] == word[0] and backtrack(r, c, 0):
                    return True
        
        # 단어 못찾으면
        return False

 

최적화 추가

 

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:    	        
        ROWS, COLS = len(board), len(board[0])
        visit = set()

		
        # ******** 최적화 추가 ******** 
        # 단어 길이와 보드 문자 빈도로 사전 필터링
        if len(word) > ROWS * COLS:
            return False
        
        word_count = Counter(word)
        board_count = Counter(char for row in board for char in row)
        for char in word_count:
            if word_count[char] > board_count.get(char, 0):
                return False
        # ******** 최적화 추가 ******** 

        def backtrack(r, c, index):
            # 단어의 모든 문자를 찾았을 경우 True 반환
            if index == len(word):
                return True

            # 현재 위치가 유효하지 않거나, 
            # 이미 방문했거나, 
            # 문자가 일치하지 않을 경우 False 반환
            if (r < 0 or r >= ROWS or c < 0 or c >= COLS or 
                (r, c) in visit or board[r][c] != word[index]):
                return False

            # 현재 좌표 방문 표시
            visit.add((r, c))

            for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                if backtrack(r+dr, c+dc, index+1):
                    return True
                
            # 방문 표시 제거
            visit.remove((r, c))
            return False

        # 모든 셀에서 탐색 시작
        for r in range(ROWS):
            for c in range(COLS):
                # 첫째 단어에서 시작해서, True 반환 받은 경우만, True 반환 
                if board[r][c] == word[0] and backtrack(r, c, 0):
                    return True
        
        # 단어 못찾으면
        return False

 

1. if len(word) > ROWS * COLS:

 

2. word_count와 board_count 계산

3. 문자 빈도 비교

최적화 효과

이 사전 필터링은 탐색을 시작하기 전에 불가능한 경우를 빠르게 제거하므로, 불필요한 백트래킹 호출을 줄여 성능을 크게 향상시킬 수 있습니다.

• 보드 크기가 크고 단어가 복잡한 경우에 효과적입니다.
• 예를 들어, 보드가 매우 크더라도 단어에 필요한 문자가 충분히 없다면 즉시 종료됩니다.

 

내 코드

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 중복 안되니, visited 로 [r, c] 좌표 체크 해야함
        ROWS = len(board)
        COLS = len(board[0])

        visited = set()

        def backtrack(r, c, i):
            if i == len(word): # 다 찾으면
                return True

            if not (0<= r < ROWS and 0<= c < COLS and (r, c) not in visited and board[r][c] == word[i]):
                return False

            # 현재 좌표 방문 표시
            visited.add((r, c))

            for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                if backtrack(r+dr, c+dc, i+1): # true
                    return True
            
            # 현재 좌표 방문 표시 제거
            visited.remove((r, c))

            return False

        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == word[0] and backtrack(r, c, 0): # True
                    return True

        return False