LeetCode Word Search (JavaScript), DFS

링크 : https://leetcode.com/problems/word-search/description/

문제 설명

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.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

---

문제 풀이

DFS를 이용하여 풀이

dfs 인자로 x좌표, y좌표, 길이를 넘김

상, 하, 좌, 우 방향으로 이동할 수 있는 경우는 현재 len에 해당하는 단어가 이동하려는 board의 단어와 일치할 때 dfs를 타고 들어갈 수 있도록 설정

한 번만 방문하기 위해 원본 단어를 저장해두고 임시로 다른 단어로 변환, 이후 다시 원본 단어로 board를 변경하는 방식

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    const directions = [[-1, 0], [0, 1], [0, -1], [1, 0]];

    const dfs = (x, y, len) => {
        if (len === word.length) {
            return true;
        }

        const originWord = board[y][x];

        board[y][x] = '#';

        for (const [dy, dx] of directions) {
            const moveX = x + dx;
            const moveY = y + dy;

            if (moveX >= 0 && moveX < board[0].length && moveY >= 0 && moveY < board.length) {
                if (board[moveY][moveX] === word[len]) {
                    if (dfs(moveX, moveY, len + 1)) {
                        return true;
                    }
                }
            }
        }

        board[y][x] = originWord;
        return false;
    }

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (word[0] === board[i][j]) {
                if (dfs(j, i, 1)) {
                    return true;
                }
            }
        }
    }

    return false;
};

---

결론

DFS를 이용하여 재귀를 돌 수 있는 조건을 잘 설정해야 함.

또한, 임시로 다른 단어로 변경하여 관리함으로 써 같은 크기의 배열을 굳이 생성할 필요가 없어 메모리 절약