[leetcode] 79

• backtracking template 기억하기
• (1) bottom case check
  (2) 해당 포지션의 valid check
  (3) 해당 포지션에서 가지칠 수 있는 경우에 대해 recursion 수행
  (4) recursion 수행 전 후로 상태 마킹 / 복원
• graph 문제의 경우, 조건을 만족한 위치를 '#'등으로 마킹하고 recursion 탐색 후
  다시 원래 map 상태로 복원하기

def backtrack(candidate):
    if find_solution(candidate):
        output(candidate)
        return
    
    # iterate all possible candidates.
    for next_candidate in list_of_candidates:
        if is_valid(next_candidate):
            # try this partial candidate solution
            place(next_candidate)
            # given the candidate, explore further.
            backtrack(next_candidate)
            # backtrack
            remove(next_candidate)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        dx = [0, 0, 1, -1]        
        dy = [1, -1, 0, 0]        
        sizex = len(board)
        sizey = len(board[0])
        def backtrack(x, y, suffix):
            # bottom case
            if len(suffix) == 0:                                
                return True
            
            
            # valid check
            # Do valid check before recursion
            if x < 0 or x >= sizex:
                return False
            if y < 0 or y >= sizey:
                return False
            if board[x][y] != suffix[0]:
                return False
            
            # set state
            board[x][y] = '#'
            
            # recursion
            ret = False
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                ret = backtrack(nx, ny, suffix[1:])
                if ret:
                    break
                    
            # recover state
            board[x][y] = suffix[0]
            
            return ret
            
        
        for i in range(sizex):
            for j in range(sizey):
                ret = backtrack(i, j, word)                
                if ret:
                    return True
        return False