LeetCode [79]: Word Search

📌 LeetCode [79]: Word Search

🔗 문제 링크

---

문제 설명 📄

2D 보드 board와 문자열 word가 주어집니다. 보드에서 상하좌우로 이동하며 word를 만들 수 있는지 확인하는 문제입니다.

• 각 글자는 보드에서 반드시 연속적으로 연결되어 있어야 하며, 한 글자는 한 번만 사용할 수 있습니다.
• board에는 알파벳 대문자가 포함되며, word도 알파벳 대문자로 구성됩니다.

---

문제 접근 방식 📋

1. 백트래킹(Backtracking):
   • 보드의 각 셀에서 시작하여, 해당 셀이 word의 현재 글자와 일치하면 재귀적으로 다음 글자를 확인합니다.
   • 이미 방문한 셀은 임시로 마킹하고, 탐색이 끝난 후 복원합니다.
2. 경계 조건:
   • 현재 셀이 보드 범위를 벗어나거나 이미 방문했거나, 현재 글자와 word의 글자가 일치하지 않으면 종료합니다.
3. 효율성:
   • 보드의 각 셀을 시작점으로 탐색하므로, 최악의 경우 모든 셀에서 word의 길이만큼 탐색합니다.

---

Solution 💻

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row, col = len(board), len(board[0])
        wordLen = len(word) - 1

        def backtracking(x, y, target):
            if board[x][y] != word[target]:
                return False

            if target == wordLen:
                return True

            temp = board[x][y]
            board[x][y] = "#"

            for px, py in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                dx, dy = x + px, y + py
                if 0 <= dx < row and 0 <= dy < col and board[dx][dy] != "#":
                    if backtracking(dx, dy, target + 1):
                        return True

            board[x][y] = temp
            return False

        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0]:
                    if backtracking(i, j, 0):
                        return True

        return False

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(m * n * 4^k)
  • m과 n은 보드의 행과 열 크기, k는 word의 길이입니다.
  • 각 셀에서 시작하여 최대 4방향으로 탐색하므로, 최악의 경우 4의 지수 형태로 증가.
• 공간 복잡도: O(k)
  • 재귀 호출 스택의 깊이는 word의 길이에 비례.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row, col = len(board), len(board[0])
        wordLen = len(word)

        def backtracking(x, y, target):
            if target == wordLen:
                return True
            if x < 0 or x >= row or y < 0 or y >= col or board[x][y] != word[target]:
                return False

            temp = board[x][y]
            board[x][y] = "#"

            result = any(
                backtracking(x + dx, y + dy, target + 1)
                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]
            )

            board[x][y] = temp
            return result

        for i in range(row):
            for j in range(col):
                if backtracking(i, j, 0):
                    return True

        return False

---

리팩토링 코드의 차이점

1. 조건문 간소화:
   • 범위 및 매칭 조건을 한 번에 처리하여 가독성 개선.
2. any 함수 사용:
   • 4방향 탐색을 any 함수로 처리하여 코드 간결화.

시간 복잡도

• 시간 복잡도는 기존 코드와 동일: O(m * n * 4^k).
• 공간 복잡도 역시 동일: O(k).

---