LeetCode - 79. Word Search (python)

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

• 난이도 : medium
• 알고리즘 : 백트래킹

접근방법

• 전형적인 백트래킹 문제, board를 순차 탐색하며 word의 첫 문자와 일치하는 좌표부터 dfs와 백트래킹을 이용하여 True False를 판단

소스코드

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        dy = [-1, 1, 0, 0]
        dx = [0, 0, -1, 1]
        stack = []
        visited = [[0 for _ in range(n)] for _ in range(m)]

        def dfs(y: int, x: int, depth: int):
            if depth == len(word):
                return True

            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if 0 <= ny < m and 0 <= nx < n and board[ny][nx] == word[depth]:
                    if not visited[ny][nx]:
                        visited[ny][nx] = 1
                        if dfs(ny, nx, depth + 1):
                            return True
                        visited[ny][nx] = 0

            return False

        for y in range(len(board)):
            for x in range(len(board[0])):
                if board[y][x] == word[0]:
                    visited[y][x] = 1
                    if dfs(y, x, 1):
                        return True
                    visited[y][x] = 0

        return False