BFS를 이용한 primPassword 찾기

 

문제 내용 : 

현재의 비밀번호를 새 비밀번호로 변경하는데 필요한 최소 동작의 수를 리턴하는것 

 

조건 : 

- 1000이상의 숫자 

- 한 번에 한 개의 숫자만 변경 가능 

- 4자리의 소수인 비밀번호로만 변경 가능 

 

풀이 과정 : 

처음에는 BFS 알고리즘 적용하여 풀생각을 못하여 무작정 풀었지만 

몇개의 테스트 케이스 밖 에 통과하지 못하였다 

 

이후 너비 탐색사용하여  모든 경우의 수를 찾으면서 최소한의 접근이 필요했으며 

그 과정속에서 조건에 맞을때 방문 FLAG 변경과 조건2에 부합하는 count를 증가시켜서 최소한의 접근과 모든 경우의 수를 판별하여 newPwd를 찾아 낼수있었다 

 

 

풀이 코드 : 

const primePassword = (curPwd, newPwd) => 
{
  if(curPwd === newPwd)
    return 0;
    
    let queue = [];
    let front = 0; // first
    let rear = 0;  // 
    let visited = Array(9999);
    visited.fill(false);
    
    const EnQueue = (queue,data) => {
        queue.push(data);
        rear++;
    }
    const DeQueue = () => {
        return queue[front++];
    }
    
    const isEmpty = (queue) => {
        if(front === rear)
            return true;
        else
            return false;
    }
    // init 
    EnQueue(queue,[0,curPwd]);

    // search 
    while(isEmpty(queue) === false)
    {
        //순회 
        const [ctr,num] = DeQueue();
        // 맨앞부터 하나씩 
        for(var i = 0 ; i < 4 ; i++)
        {
            var target = toArray(num);
             // 0~9 까지 대입 
            for(var j = 0 ; j <= 9 ; j++)
            {
                // 대입한 숫자가 현재 target이랑 같으면 change x 
                if(j === target[i]){
                    continue;
                }
                 // 완벽 복사 
                let result = target.slice();
                result[i] = j;
                result = toDigits(result);
                
                   //만약 newpwd를 찾았다면?
                if(result === newPwd){
                   
                    return ctr+1;
                }

                 // 못찾으면 조건에 부합하는 소수 queue에 넣어서 다시 확인  
                if(result >= 1000 && PrimeCheck(result) === true && visited[result] === false)
                {
                  visited[result]=true;
                  EnQueue(queue,[(ctr+1),result]);
                }
              
                //console.log(j+"---"+result[i]+"---"+result)
                
            }        
           
        }
        
        
      
 
    }
};

// 소수 검증 
function PrimeCheck(num)
{
    for(var i=2; i*i <= num; i++)
    {
        if(num % i == 0) 
            return false;
    }
    return true;
}
function toDigits(array){ // 배열 -> 숫자로 
   return Number(array.join(''));
}

function toArray(num){ // 숫자 -> 배열 
    return num.toString().split('').map(item=>parseInt(item))    
}

 

모든 테스트 케이스에 통과하였으며 다음엔 BFS에 포스팅을 해볼려한다