BFS와 Queue를 활용한 primePassword 관련 문제 Javascript

문제

다음의 조건을 만족하면서 현재의 비밀번호('curPwd')를 새 비밀번호(newPwd)로 변경하는 데 필요한 최소 동작의 수를 리턴해야 합니다.

• 한 번에 한 개의 숫자만 변경가능하다.
• 4자리의 소수(prime)인 비밀번호로만 변경가능하다.
  정리하면, 비밀번호가 계속 소수를 유지하도록 숫자 한 개씩을 바꿔갈 때 현재 비밀번호에서 새 비밀번호로 바꾸는 데 최소 몇 개의 숫자를 변경해야 하는지를 리턴해야 합니다.

주의 사항

4자리인 소수는 1,000 이상의 소수를 말합니다.(0011, 0997 등은 제외)

입출력 예시

let output = primePassword(1033, 1033);
console.log(output); // --> 0

output = primePassword(3733, 8779);
console.log(output); // --> 3 (3733 -> 3739 -> 3779 -> 8779)

풀이

// 소수를 판별하는 방법
const checkPrime = (num) => {
	if(num % 2 === 0) return false;
    let sqrt = parseInt(Math.sqrt(num));
    for(let divider = 3; divider <= sqrt; divider += 2){
    	if(num % divider === 0){
        	return false;
        }
    }
    return true;
}

// 각 자릿수 변경을 위해 번호를 split해서 쪼개버립니다.
const splitNum = (num) => {
	const digits = num.toString().split("");
    return digits.map((el) => Number(el));
}

// 변경된 숫자를 다시 join을 통해 합쳐줍니다.
const joinDigits = (digits) => Number(digits.join(""));

const primePassword = (curPwd, newPwd) => {
	// 현재 비밀번호와 바뀐 비밀번호가 같다면 0을 반환합니다.
    if(curPwd === newPwd) return 0;
    
    let head = 0;
    let tail = 0;
    const queue = [];
    
    const enQueue = (queue, item) => {
    	queue.push(item);
        tail++;
    }
    
    const deQueue = (queue) => queue[head++];
    
    const isEmpty = (queue) => head === tail;
    
    enQueue(queue, [0, curPwd]);
    // 방문 기록은 전부 false를 채워둔다.
    const isVisited = Array(10000).fill(false);
    isVisited[curPwd] = true;
    
    while(!isEmpty(queue)){
    	const [step, num] = deQueue(queue);
        for(let i = 0; i < 4; i++){
        	const digits = splitNum(num);
            for(let j = 0; j < 10; j++){
            	if(j !== digits[i]){
                	digits[i] = j;
                    const next = joinDigits(digits);
                    if(next === newPwd){
                    	return step + 1;
                    }
                    if(next > 1000 && checkPrime(next) && !isVisited[next]){
                    	isVisited[next] = true;
                        enQueue(queue, [step + 1, next]);
                    }
                }
            }
        }
    }
    return -1;
}

풀이에 앞서, 소수를 판별하는 함수를 만들었고, 각 자릿수 변경을 위해 split 활용 후 join을 통해 합쳐줬습니다. 여기까지는 쉽게 생각할 수 있었고 문제는 Queue에 대한 활용이 어려웠습니다.

BFS, Queue를 통해 최소 변경 횟수를 구해야합니다.

const PrimePassword을 시작으로 while문까지의 작성이 제일 중요하지만, 정작 제일 중요한 부분 작성을 못했다. 프로그래머스 카카오 문제에 비슷한 문제가 보였고, 백준을 통해 관련 문제를 많이 풀어보는게 중요해보인다.

console도 찍어보고, 손코딩도 해본 결과.. 예시로 console 찍었을 때, 엄청나게 많은 경우의 수가 발생한다. 천천히 읽어보자.