View in English →

Code › algorithm-study

LeetCode 79 - Word Search

보드에 방문 상태를 직접 표시하며 단어 경로를 탐색한 DFS backtracking Python 풀이

algorithmleetcodebacktrackingdfsmatrixgridrecursionstringpythonlearning

이 문제를 오랜만에 다시 보게 되었는데 어? 생각보다 쉽겠는데? DFS 적용하면 금방이겠군 하고 생각했으나 문제를 푸는 알고리즘보다 최적화나 코드 자체에 대한 부분에서 생각이 좀 많아진 문제였다.

문제 자체는, 문자 보드에서 상하좌우로 인접한 칸을 이어 주어진 단어를 만들 수 있는지 확인하는 Medium 문제다. 모든 칸을 시작점으로 확인하되, 한 경로에서 같은 칸을 다시 사용할 수 없도록 보드를 임시로 변경하고 탐색이 끝나면 원래 값으로 복구했다.

문제 링크 & 설명

  • 문제 링크: 79. Word Search
  • 요약: m × n 문자 보드와 문자열 word가 주어졌을 때, 상하좌우로 인접한 칸을 따라 word를 만들 수 있으면 true를 반환하는 문제. 하나의 칸은 같은 경로에서 두 번 사용할 수 없다.

단어의 첫 글자는 보드 어디에나 있을 수 있으므로 모든 좌표에서 DFS를 시작해야 한다. 현재 좌표의 문자가 word의 현재 글자와 같을 때만 다음 글자를 찾으러 현재 위치 기준 위, 아래, 왼쪽, 오른쪽 이렇게 네 방향으로 이동한다.

접근 방법

DFS 상태는 현재 행과 열, 그리고 word에서 확인할 인덱스로 구성했다. 좌표가 보드 범위를 벗어나거나 현재 문자와 일치하지 않으면 해당 경로를 종료한다.

if row < 0 or col < 0 or row >= len(board) or col >= len(board[0]):
    return False

if word_idx >= len(word) or board[row][col] != word[word_idx]:
    return False

현재 문자가 단어의 마지막 글자라면 전체 단어를 찾은 것이므로 true를 반환한다. 아직 글자가 남아 있다면 현재 칸을 #으로 바꿔 같은 경로에서 재사용되지 않도록 표시한다.

temp = board[row][col]
board[row][col] = '#'

이후 상하좌우 네 방향 중 하나라도 나머지 단어를 찾으면 성공이다. 탐색 결과를 저장한 다음 현재 칸을 원래 문자로 복구해야 다른 시작점이나 다른 경로에서도 사용할 수 있다.

found = (
    self.dfs(board, word, row + 1, col, word_idx + 1) or
    self.dfs(board, word, row - 1, col, word_idx + 1) or
    self.dfs(board, word, row, col + 1, word_idx + 1) or
    self.dfs(board, word, row, col - 1, word_idx + 1)
)

board[row][col] = temp
return found

단어 길이가 보드의 전체 칸 수보다 길면 어떤 경로로도 만들 수 없으므로, row_len과 column_len, word_len을 구한 뒤 DFS를 시작하기 전에 false를 반환했다. 이 최적화는 나중에 찾아보면서 적용하게 되었는데 좋은 발상?? 이라고 할 수 있었다 ㅎㅎ

트러블 슈팅

처음에는 보드와 같은 크기의 2차원 visited 배열을 만들어 현재 경로에서 방문한 칸을 관리했는데, 이후 현재 칸의 문자를 #으로 임시 변경하면 이미 방문한 칸이 다음 문자와 일치하지 않으므로 별도 배열 없이도 중복 방문을 막을 수 있다는 것을 알게 됐다.

복잡도 분석

  • 시간 복잡도: O(m × n × 3^w)
    • 각 칸에서 탐색을 시작할 수 있고, 첫 이동 이후에는 바로 이전 칸을 다시 사용할 수 없어 각 단계에서 최대 세 방향으로 분기한다. w는 word의 길이다. 복잡도 분석을 좀 깊게 생각해보며 이해해본 문제였다.
  • 공간 복잡도: O(w)
    • 보드에 방문 상태를 직접 표시하므로 별도 방문 배열은 없고, 재귀 호출 스택이 단어 길이만큼 쌓일 수 있다.

구현 코드

from typing import List

class Solution:
    def dfs(
        self,
        board: List[List[str]],
        word: str,
        row: int,
        col: int,
        word_idx: int,
    ) -> bool:
        if row < 0 or col < 0 or row >= len(board) or col >= len(board[0]):
            return False

        if word_idx >= len(word) or board[row][col] != word[word_idx]:
            return False

        if word_idx == len(word) - 1:
            return True

        temp = board[row][col]
        board[row][col] = '#'

        found = (
            self.dfs(board, word, row + 1, col, word_idx + 1)
            or self.dfs(board, word, row - 1, col, word_idx + 1)
            or self.dfs(board, word, row, col + 1, word_idx + 1)
            or self.dfs(board, word, row, col - 1, word_idx + 1)
        )

        board[row][col] = temp
        return found

    def exist(self, board: List[List[str]], word: str) -> bool:
        row_len = len(board)
        column_len = len(board[0])
        word_len = len(word)

        if row_len * column_len < word_len:
            return False

        for i in range(row_len):
            for j in range(column_len):
                if self.dfs(board, word, i, j, 0):
                    return True

        return False

요약 및 회고

이번 문제는 생각보다 만족스러운 문제였다. DFS의 응용과 최적화, 그리고 backtracking의 최적화와 시간복잡도 분석까지 나름 깊게 생각해 볼 수 있는 문제였기 때문이다. 무심코 문제만 풀고 넘어가면 좋은 인사이트를 남길 수 없어서 요즘엔 조금이라도 생각을 해보고 넘어가려고 한다.