[LeetCode] 79. Word Search - Python 풀이

스키장 갔다와서 오랜만에 릿코드 풀이! 

확실히 여행 다녀오니까 머리가 잘 돌아간다 

https://leetcode.com/problems/word-search/?envType=study-plan-v2&envId=top-interview-150

Word Search - LeetCode

 

해당하는 단어가 현재 N*M 크기의 board 내부에 들어있는지 여부를 체크하는 함수를 작성하면 된다. 

이 경우 모든 경우를 확인해봐야 하므로, 알파벳의 길이를 하나씩 늘렸다가 줄인후에 다른 알파벳을 붙여보는 backtracking 기법을 사용했다. 주의할 점은 이미 방문한 칸은 방문여부를 저장해두어야 한다는 점으로, 이를 위해 visited 라는 2차원 배열 공간을 사용했다. 

# https://leetcode.com/problems/word-search/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        global flag
        N = len(board)
        M = len(board[0])
        visited = [[False] * M for _ in range(N)]
        s = word[0] # initial alphabet

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

        def dfs(x, y, arr, idx, visited):
            global flag
            nw = "".join(arr)
            if len(nw) == len(word):
                flag = True
                return
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]

                if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                    ch = board[nx][ny]

                    if word[idx] == ch:
                        arr.append(ch)
                        visited[nx][ny] = True
                        dfs(nx, ny, arr, idx+1, visited)
                        visited[nx][ny] = False
                        arr.pop()

        flag = False
        for i in range(N):
            for j in range(M):
                if board[i][j] == s and not visited[i][j]:
                    visited[i][j] = True
                    dfs(i, j, [s], 1, visited)
                    visited[i][j] = False

        return flag