[Algorithm] BFS Queue 자바스크립트(primePassword 문제) 구현

 

 

primePassword 문제는 궁극적으로 BFS 알고리즘을 사용합니다. BFS 알고리즘에서는 Queue 자료구조를 사용하며, queue가 빈 배열이 될 때 까지 while문으로 반복을 진행합니다. Java에서는 queue 자료구조를 지원하지만 JS에서는 배열을 이요해 구현하는 과정이 별도로 필요합니다.

 

 

문제

 

특정 조건을 만족한 현재 비밀번호를 새로운 비밀번호로 변경하는데 필요한 최소한의 과정의 수를 반환하세요. 비밀번호는 계속 소수인 상태를 유지해야 하고, 숫자를 한개씩 바꿔나갈 때 최소 몇번의 숫자가 변경되어야 하는지를 반환해야 합니다.

• 한번에 한개의 숫자만 변경 가능합니다.
• 4자리의 소수인 비밀번호로만 변경이 가능합니다.

 

현재 비밀번호는 number 타입의 자연수 (1000 <= number <= 9999)

새로운 비밀번호는 number 타입의 자연수 (1000 <= number <= 9999)

 

4자리의 소수는 1000 이상의 소수입니다.

 

문제 정리

처음 문제를 보고 쉽게 이해가 되지 않습니다. 소수로만 구성된 비밀번호로 새로운 비밀번호 변경을 한다면 for 반복문을 curPwd 부터 newPwd까지 돌리면서 prime(소수) 여부만 체크하면 되겠지 했는데, 문제에서 물어보는건 그게 아닙니다. 숫자를 한개씩 변경해야 하고, 각 과정의 숫자가 모두 소수여야 합니다. 

 

풀이

 

이번 문제는 주어진 curPwd를 4개의 부분으로 나누어 생각해봐야 합니다. 각 자리수는 개별적으로 변경이 되어야 하고, 소수여야 한다는 조건이 붙기 때문입니다. 따라서 숫자를 4개 요소를 가진 배열로 나누고, 각 자리수를 변경하면서 새로운 비밀번호와 비교해야 합니다.

 

curPwd를 파싱하고, 각 자리수를 1부터 9까지 반복하면서 여러 조건값들을 비교합니다. 만약 소수인 상태면서, 이전에 사용하지 않았고, 1000이상의 숫자라면 교체 가능한 비밀번호 범주안에 들어가게 됩니다. 이 과정을 계속 반복해야 하는데, 트리 구조로 풀이 과정을 그려보면 아래 그림과 같습니다.

 

 

리프 노드로 바로 빠지지 않고, 루트 노드에 걸쳐진 모든 노드를 순회하면서 조건값을 찾는 과정이므로, BFS 알고리즘을 사용하면 적절한 해답을 찾을 수 있습니다. BFS 알고리즘을 사용하기 위해, queue 자료구조를 사용하고, 방문기록을 남길 수 있는 visit 배열을 생성합니다. 마지막으로 모든 노드를 순회하기 위해 while 반복문을 사용합니다.

 

 

유효성 검사 함수 생성

소수인지 여부를 체크할 수 있는 함수, 숫자를 4자리 숫자 배열로 변경하는 함수, 마지막으로 4자리 숫자 배열을 하나의 숫자로 통합해주는 함수 3가지 함수를 구현합니다.

 

// 배열을 숫자로 변경
function joinDigits(digits){
    Number(digits.join(''));
}

// 소수인지 확인
function checkPrime(n){
    for(let i=2; i<n; i++){
        if(n % i === 0) return false;
    }
    return true;
}

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

 

Queue 자료구조 구성

BFS 알고리즘을 사용하기 위해 queue 자료구조를 기본 구성합니다. 큐는 앞뒤로 2개의 queue pointer가 붙게 됩니다. 또한 새로운 요소를 입력할 때는 뒤로 입력되고, 출력은 앞으로 되는 FIFO 구조이므로 데이터 입출력 함수인 enQueue와 deQueue 2가지 함수를 구현합니다.

 

추가적으로 queue가 빈 상태를 체크할 수 있는 함수를 작성해야 합니다. queue가 비었다는 것은 rear, front 2개의 queue pointer가 같아지는 경우를 의미합니다. 마지막으로 순환 과정에서 반복을 제거하기 위해 visit 배열을 생성합니다. 가능한 숫자의 범위가 1000~9999이므로 총 1만개의 Boolean 요소를 가진 배열을 생성합니다.

 

// Queue Data Structure
const queue = [];

// Queue Pointer
let rear = 0;
let front = 0;

// rear === front 인 경우 queue가 비었다는 뜻.
const isEmpty = (queue) => rear === front;

// 데이터 삽입 함수
const enQueue = (queue, item) =>{
    queue.push(item);
    rear++;
}

// 데이터 출력 함수
const deQueue = () =>{
    return queue[front++];
}

// 방문 기록 배열
const visited = Array(10000).fill(false);

 

Qeueue 기본구성을 마치고 최초 데이터를 입력합니다. 

enQueue(queue, [0, curPwd]);
visited[curPwd] = true;

 

BFS 핵심 로직 구성

newPwd를 찾기 위해 while문으로 queue가 빌 때 까지 반복합니다. 주어진 num의 4자리수를 순회하면서 0부터 9까지 숫자를 교체해나가면서 newPwd를 찾습니다. 만약 찾지 못하는 경우 -1을 반환하고, 찾는 경우 계속 증가하는 cnt+1을 출력합니다. 

 

while(isEmpty(queue) === false){
    const [ cnt, num ] = deQueue(queue);

    for(let i=0; i<4; i++){
        const digits = toArray(num);
        for(let j=0; j<10; j++){
            if(j !== digits[i]){
                digits[i] = j;
                const next = joinDigits(digits);

                if(next === newPwd) return cnt+1;

                if(next > 1000 && checkPrime(next) && visited[next]===false){
                    visited[next] = true;
                    enQueue(queue, [cnt+1, next]);
                }
            }
        }
    }
}
return -1;

 

 

Javascript Code

function primeP(curPwd, newPwd){
    if(curPwd === newPwd) return 0;

    let rear = 0;
    let front = 0;
    const queue = [];
    const isEmpty = (queue) => rear === front;
    
    const enQueue = (queue, item) =>{
        queue.push(item);
        rear++;
    }
    const deQueue = () =>{
        return queue[front++];
    }

    const visited = Array(10000).fill(false);

    enQueue(queue, [0, curPwd]);
    visited[curPwd] = true;

    while(isEmpty(queue) === false){
        const [ cnt, num ] = deQueue(queue);

        for(let i=0; i<4; i++){
            const digits = toArray(num);
            for(let j=0; j<10; j++){
                if(j !== digits[i]){
                    digits[i] = j;
                    const next = joinDigits(digits);

                    if(next === newPwd) return cnt+1;

                    if(next > 1000 && checkPrime(next) && visited[next]===false){
                        visited[next] = true;
                        enQueue(queue, [cnt+1, next]);
                    }
                }
            }
        }
    }
    return -1;
}
  
function joinDigits(digits){
    Number(digits.join(''));
}

function checkPrime(n){
    for(let i=2; i<n; i++){
        if(n % i === 0) return false;
    }
    return true;
}

function toArray(num){
    return num.toString().split('').map(item=>parseInt(item))    
}



const output = primeP(1009, 1171);
console.log(output); // 5

 

 

 

[Backtracking] 백준 15651 N과 M 3단계 Node.js 구현하기

 

[Algorithm] treeBFS 알고리즘 Javascript Node.js 구현하기

 

[Algorithm] Binary Search 알고리즘 Javascript (반복, 재귀, 트리구조)