[Python][backtracking] Word Search - LeetCode #79

[문제]

 

 

[느낀점 / 깨달은점]

• Backtracking 문제이다.
• 방문체크 배열을 재귀함수의 내부 재귀함수로 들어갈 때마다 deep copy를 해주었는데, 이렇게 하면 Time Limit !
  • deep copy보다는 하나의 방문체크 배열을 사용하고, 내부 재귀함수 후 False(방문하지 않음)로 돌려주는 방법.
  • feat. binue

 

[코드]

class Solution:
    
    result = False

    def exist(self, board: List[List[str]], word: str) -> bool:
        def print_2d( a):
            for i in a :
                for j in i:
                    print(j, end=' ')
                print()

        def back_tracking(i, j, num, is_used):
            if num == len(word):
                self.result = True
                return 

            for n in range(4):
                ii = i + dy[n]
                jj = j + dx[n]

                if ii < 0 or jj < 0 or ii >= H or jj >= W or is_used[ii][jj]:
                    continue

                if board[ii][jj] == word[num] :
                    import copy 
                    # is_used_temp = copy.deepcopy(is_used)
                    # is_used_temp[ii][jj] = True
                    # back_tracking(ii, jj, num+1, is_used_temp)

                    is_used[ii][jj] = True
                    back_tracking(ii, jj, num+1, is_used)
                    is_used[ii][jj] = False
            
        num = 0
        H = len(board)
        W = len(board[0])

        dy = [-1, 1, 0, 0]
        dx = [0, 0, -1, 1]

        is_used = [[False for _ in range(W)] for _ in range(H)]

        for i in range(H):
            for j in range(W):
                if board[i][j] == word[0]:
                    is_used[i][j] = True
                    back_tracking(i, j, 1, is_used)
                    if self.result : 
                        return True
                    is_used[i][j] = False
        return False