[LeetCode] 79. Word Search

해당 문제는 현재 위치를 기준으로 dfs를 실행하며 인접한 셀들을 검사할 수 있는가를 판별하는 문제이다.

😎풀이

function exist(board: string[][], word: string): boolean {
    const moveY = [-1, 0, 1, 0]
    const moveX = [0, 1, 0, -1]
    
    for(let i = 0; i < board.length; i++) {
        for(let j = 0; j < board[i].length; j++) {
            if(board[i][j] === word[0] && dfs(0, i, j, new Set())) return true
        }
    }

    function dfs(curIdx: number, curY: number, curX: number, visited: Set<string>): boolean {
        if(curIdx === word.length) return true;
        
        if(!isValidPos(curY, curX) || visited.has(`${curY},${curX}`) || board[curY][curX] !== word[curIdx]) {
            return false;
        }
        
        visited.add(`${curY},${curX}`);
        
        for(let i = 0; i < 4; i++) {
            const nextY = curY + moveY[i];
            const nextX = curX + moveX[i];
            if(dfs(curIdx + 1, nextY, nextX, visited)) {
                return true;
            }
        }
        
        visited.delete(`${curY},${curX}`);
        return false;
    }

    function isValidPos(curY: number, curX: number): boolean {
        return curY >= 0 && curY < board.length && curX >= 0 && curX < board[0].length;
    }

    return false
};