[DSA][Backtracking] 07. Word Search

LeetCode 79

 

07. Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring.
The same letter cell may not be used more than once.

 

 

[아이디어]

- board에서 word의 첫 글자와 일치하는 칸을 시작점으로, DFS를 사용해 상·하·좌·우로 탐색하며 word를 순서대로 탐색한다.

 

 

[풀이 1] Backtracking

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        visited = [[False for _ in range(COLS)] for _ in range(ROWS)]

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
                word[i] != board[r][c] or visited[r][c]):
                return False

            visited[r][c] = True
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
            visited[r][c] = False
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

이 문제는 전형적인 DFS + Backtracking 문제이다.

먼저 board 전체를 순회하면서, 현재 칸의 문자가 word의 첫 글자와 같은 경우에만 DFS를 시작한다. DFS 함수는 현재 위치 (r, c)와 word에서 매칭 중인 인덱스 idx를 인자로 받아서 현재 위치에서 상, 하, 좌, 우 네 방향으로 이동하며 다음 문자를 찾는다.

보드 범위를 벗어나지 않으면서, 아직 방문하지 않은 칸이면서, 해당 칸의 문자가 word[idx]와 같다면 해당 칸을 방문 처리하고, 다음 인덱스로 DFS를 재귀 호출한다. 만약 네 방향을 모두 탐색했는데 word를 완성하지 못했다면, 다른 경로를 탐색할 수 있도록 방문 처리를 되돌린다.(backtracking)

 

 

⏱️ 시간복잡도

board의 크기를 n × m, word의 길이를 L이라고 하면, 최악의 경우 모든 칸을 시작점으로 DFS를 수행하게 된다. 각 시작점에서 DFS는 최대 L의 깊이를 가지고, 매 단계마다 상·하·좌·우 최대 4개의 방향으로 분기할 수 있다. 따라서 전체 시간 복잡도는 O(n × m × 4^L) 이다.

​

🧠 공간복잡도

visited 배열이 board와 동일한 크기인 n × m 공간을 사용하므로 O(n × m) 공간이 필요하다. (DFS의 최대 깊이는 word의 길이 L이므로 재귀 호출 스택은 O(L) 공간을 사용하지만, 일반적으로 n x m이 크기 때문에 생략)