[알고리즘 개념] 백트래킹

 

* 아래 내용은 바킹독의 실전 알고리즘을 듣고 정리한 내용입니다 *

 

 

백트래킹 알고리즘은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘입니다.

백트래킹은 상당한 구현력을 필요로 하며 사소한 부분에서 실수하기 쉽습니다. 또 재귀의 특성상 틀린 부분을 찾는 것도 어렵습니다. 따라서 많은 시간을 할애하여 개념을 익히고 연습하는게 중요합니다.

그렇지만 응용 건덕지가 많지 않으므로, 예제를 꼼꼼하게 풀고 기본적인 코드 형태를 익혀두면 할 만 할 것입니다.

바킹독님이 작성하신 BOJ 15649번 코드를 javascript 코드로 변경하였습니다.

기본 코드

let N, M;

let arr = Array(10).fill(0);
let isUsed = Array(10).fill(false);

function backTracking(k) {

    // base line : arr가 모두 채워진 경우(k가 arr의 인덱스 범위를 넘어간 경우)
    if(k === M) {
        console.log(arr.slice(0, M).join(' '));
        return;
    }
    
    for(let i = 1; i <= N; i ++) { // 1부터 N까지의 수에 대해

        if(!isUsed[i]) { // 아직 i가 사용되지 않았으면
            
            arr[k] = i; // k번째 수를 i로 정한다.
            isUsed[i] =true; // i가 사용됐음을 표시
            backTracking(k + 1); // 다음 자릿 수를 정하러 한 단계 더 들어간다.
            isUsed[i] = false; // k번째 수를 i로 정한 모든 경우를 확인했으니 다시 사용되지 않았다고 표시
        }
    }
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (line) => {
    [N, M] = line.split(' ').map(Number);
    backTracking(0);
    rl.close();
});