[21/10/02 KATA NINJA] Word Search

내 코드

백트래킹 -> 유망하지 않으면 가지치기. (더가지않는다)

유망 조건 1 : 다음으로 탐색할 문자가 word[level]과 일치하는가 ?

유망 조건 2 : 방문하지 않은 곳인가 ?

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    
    let flag = false;
    // 상하좌우 배열
    const dx = [-1,0,1,0]
    const dy = [0,-1,0,1];
    
    DFS('',[], 0)
    
    
    return flag
    
    
    function DFS(current,visited,level,position){
        const letter = word[level];
        
        if(flag){
            return ;
        }
        
        if(current === word){
            flag = true;
        }
        
        
        if(current.length === 0){
            for(let i = 0;i<board.length;i++){
                for(let j=0;j<board[i].length;j++){
                    if(board[i][j] === letter && !visited.includes(`${i}${j}`)){
                        DFS(`${current}${letter}`,[...visited,`${i}${j}`],level+1,[i,j]);
                    }
                }
            }
        }else{
            const [x,y] = position;
            for(let i=0;i<dx.length;i++){
                const nextX = x + dx[i];
                const nextY = y + dy[i];
                
                if(board[nextX] && board[nextX][nextY] && board[nextX][nextY] === letter && !visited.includes(`${nextX}${nextY}`)){
                    DFS(`${current}${letter}`,[...visited,`${nextX}${nextY}`], level+1, [nextX,nextY]);
                }
            }  
            
        }
        
        
        
        
    }
};

방문을 체크하기 위한 배열을 사용하는 것이 비효율적으로 보여 객체를 사용하는 코드로 변경해보았다.

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    
    let flag = false;
    // 상하좌우 배열
    const dx = [-1,0,1,0]
    const dy = [0,-1,0,1];
    
    DFS('',{}, 0)
    
    // 객체의 얕은 복사는 시간이 큰가보다
    return flag
    
    
    function DFS(current,visited,level,position){
        const letter = word[level];
        
        if(flag){
            
            return ;
            
        }
        
        if(current === word){
            
            flag = true;
            return;
        }
        
        
        if(current.length === 0){
            for(let i = 0;i<board.length;i++){
                
                for(let j=0;j<board[i].length;j++){
                    
                    if(board[i][j] === letter && !visited[`${i}${j}`]){
                        
                        DFS(`${current}${letter}`,{...visited, [`${i}${j}`]:true },level+1,[i,j]);
                        
                    }
                    
                }
                
            }
            
        }else{
            
            const [x,y] = position;
            
            for(let i=0;i<dx.length;i++){
                
                const nextX = x + dx[i];
                
                const nextY = y + dy[i];
                
                if(board[nextX] && board[nextX][nextY] && board[nextX][nextY] === letter && !visited[`${nextX}${nextY}`]){
                    
                    DFS(`${current}${letter}`,{...visited,[`${nextX}${nextY}`]:true}, level+1, [nextX,nextY]);
                    
                }
            }  
            
        }
        
        
        
        
    }
};

오히려 시간초과가 나게되는데, 이유는 객체 spread 비용이 크기 때문.

개선 후 코드

var exist = function(board, word) {
    if (word.length > board.length * board[0].length) {
        return false;
    }
    // 상하좌우 배열
    const dx = [-1,0,1,0]
    const dy = [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] ){
                // 찾는 단어의 길이가 1인 경우 첫글자만 같아도 바로 답을 알아낼 수 있다.
                if(word.length === 1) return true; 
                // 찾는 단어의 길이가 1보다 크다면 뒤 글자들 까지 탐색해야하므로        
                if(DFS(1 , [i,j])) return true;
                        
            }
                    
            
        }
    }
    
    
    return false
    
    
    function DFS(level,position){
        
        const letter = word[level];
      
        const [x,y] = position;
            
        for(let i=0;i<dx.length;i++){
                
            const nextX = x + dx[i];
                
            const nextY = y + dy[i];
                
            if(board[nextX] && board[nextX][nextY] && board[nextX][nextY] === letter ){
               // level이 word.length-1이면서 다음 문자가 word[level]과 같다면 단어를 포함하고 있는 것이다.
               if(level === word.length - 1) return true; 
               
               // tmp
               const data = board[x][y]
               // 재방문 하지 않게 하기 위해 null로 변경한다.
               board[x][y] = null;
               
               // 단어를 완성하지 못했으므로 계속 탐색한다. (유망하므로)	 
               if(DFS(level+1, [nextX,nextY]) ) return true;
               // DFS를 다녀왔으므로, 다시 원래 값으로 변경한다.ㅈ 
               board[x][y] = data;     
            }
        }  
    }
};

Binary Tree Level Order Tree

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return []
    
    
    const queue = [{node : root, lev:0 }];
    const result = [];
    while(queue.length !== 0){
        const {node,lev} = queue.shift();
        
    
        if(result[lev]){
        
            result[lev].push(node.val);
        
        }else{
            result[lev] = [node.val];
        
        }
        
        if(node.left){
            queue.push({node : node.left,lev:lev+1})
        }
        if(node.right){
            queue.push({node : node.right,lev:lev+1});
        }
        
        
        
    }
    
    return result;
};