[leetcode]79. Word Search

https://leetcode.com/problems/word-search/description/
m*n 그리드 스타일의 보드가 주어지고
word가 주어지면
만약 그리드에 word가 있으면 true를 반환해라.

근접한 셀을 순서대로 구조화하여 단어가 만들어질 수 있다.
수직 혹은 수평으로 근접.

같은 문자는 한번 이상 사용될 수 없다.

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    //word를 순회해서 board의 x,y를 조절하여, 값이 있으면 계속 true
    const xLength = board[0].length;
    const yLength = board.length

    // 체크 배열: 방문 여부를 저장. 각 DFS마다 새로 초기화될 필요는 없음 (DFS 내에서 백트래킹 처리하므로)
    const check = Array.from({ length: yLength }, () => Array(xLength).fill(false));


    // 단어의 첫 글자와 일치하는 시작점을 모두 수집
    const startPoints = []
    for(let i = 0; i<xLength;i++){
        for(let j = 0; j<yLength;j++){
            if(board[j][i] == word[0]){
                startPoints.push([j,i])
            }
        }
    }
    // 각 시작점에서 DFS 시도
    for(let startPoint of startPoints){
        // 잘못된 길로 가는 경우도 있기 때문에 백트렉킹은 무조건 필요하다. 
        if(backTracking(startPoint,board,word,check)) return true
    }

    return false
};

function backTracking(startPoint,board,word,check){
    const xLength = board[0].length;
    const yLength = board.length
    const upDownLeftRight = [[-1,0],[1,0],[0,-1],[0,1]]
    //스타트 포인트부터 해서, 완성이 가능한지를 dfs를 통해서 진행한다. 
    //idx는 현재 확인해야할 word의 idx이다. 
    function dfs(y,x,idx){
        if(idx == word.length) return true
        
        if(y < 0 || y >= yLength ||
           x < 0 || x >= xLength  || 
           check[y][x] ||
           board[y][x] !== word[idx]
        ) return false;

        check[y][x] = true
        // 4방향 탐색
        for(let [dy,dx] of upDownLeftRight){
            //만약 타겟에 해당하는지를 확인을 먼저 해야할것같음!
            if(dfs(y+dy,x+dx,idx+1)) return true //4방향에 대해서 모두 dfs를 진행한다.
            
        }

        //백트레킹
        check[y][x] = false;
        return false
        
    }
    return dfs(...startPoint,0)
}

이 문제는 백트레킹으로 풀어서, 맞는 길을 찾을때까지 dfs를 진행해야하는 문제이다.
백트레킹은 check 배열이 필요한데, 사실 그냥 보드의 내용을 변경해도 된다.

시작점을 따로 두지 않고 푸는 방법도 있는 것 같은데, 이건 다음에 한번 다른 방식으로 풀어봐야겠다!