79. Word Search (Medium)

처음에 bfs로 풀었다가 크게 당했던 문제...

다 풀고나서 통과 못한 테케를 보고 백트래킹 써야하는 걸 깨달았다

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n,m = len(board), len(board[0])
        dirx,diry=[0,0,-1,1],[1,-1,0,0]
        start=[]
        for i in range(n):
            for j in range(m):
                if board[i][j] == word[0]:
                    start.append((j,i))

        def backtrack(x,y,suffix):
            # 다 찾음
            if len(suffix)==0:
                return True
            # 범위 밖으로 나갔거나 다른 글자인 경우
            if( y<0 or y==n or x<0 or x==m or board[y][x]!=suffix[0]):
                return False

            # 범위 안에 있고, 찾으려는 글자임
            f = False
            board[y][x] = '#'

            # 사방 살펴보기
            for dx, dy in zip(dirx, diry):
                f = backtrack(x+dx, y+dy, suffix[1:])

                # 다찾으면 중지
                if f:
                    break
            
            # 되돌리기
            board[y][x] = suffix[0]
            return f

        for x, y in start:
            if backtrack(x, y, word):
                return True
        return False

기본적인 백트래킹인데 2차원 배열에서 dxdy랑 섞이니까 좀 어렵다