백트래킹 (완전탐색) 알고리즘

*N과 M (1)

풀이

이 문제는 N개 중에 M개를 고르는 순열과 같은 문제
순서가 고려되는 수의 나열

function solution()
{
    let n = 4
    let m = 4
    
    let arr = [];
    for (let i=1; i<=n; i++) {
        arr.push(i) // 초기 arr : 1, 2, 3, 4
    }
    let visited = new Array(n).fill(false); // 초기 visited [false, false, false, false]
    let selected = []; // vistied 스위치 역할 + arr[i] 접근을 위한 인덱스 역할
    
    let answer = [];
    
    function dfs(arr, depth) {
        if (depth === m) { // m이 됐으면 넣기
            let result = [];
            for (let i of selected) {
                result.push(arr[i]) // arr의 인덱스에 해당하는 값들을 넣다가 길이가 4가 됐을 때 push
                if (result.length === m) answer.push(result)
            }
        }
        
        for (let i=0; i < arr.length; i++) {
            if (visited[i]) { // visitied[i]가 true, 그 수는 빼고 진행
                continue;
            }
            selected.push(i) // 인덱스를 저장하는 공간 0 1 2 3
            visited[i] = true; // 해당하는 인덱스를 넣었으면 그 인덱스는 다시 안 넣음
            dfs(arr, depth+1) // m가 될 때까지 반복
            selected.pop() // 해당 인덱스 선택 취소 
            visited[i] = false // 해당 인덱스 방문 취소 
        }
    }
    
    dfs(arr, 0)
    
    console.log(answer)
}

---

모든 순열

풀이

function solution()
{
    let n = 3;
    
    let arr = [];
    for (i=1; i<=n; i++) {
        arr.push(i)
    }
    
    let visited = new Array(n).fill(false);
    let selected = [];
    
    let ans = [];
    
    function dfs(arr, depth) {
        if (depth === n) {
            let result = [];
            for (let i of selected) {
                result.push(arr[i])
                if (result.length === n) {
                    ans.push(result)
                }
            }
        }
        
        for (let i=0; i < arr.length; i++) {
            if (visited[i]) { 
                continue 
            }
            selected.push(i)
            visited[i] = true
            dfs(arr, depth+1)
            selected.pop()
            visited[i] = false
        }
    }
    
    dfs(arr, 0)
    console.log(ans)
}

설명

위 N과 M 문제와 완전히 똑같은 로직과 코드를 사용해도 된다. 유의해야할 건 for문에서 i란 변수를 동일하게 사용 했으므로 let을 꼭 까먹지 않고 해야한다 안 그러면 겹친다.

---

*N과 M (2)

문제 해결 아이디어

1부터 N까지 자연수 중에서 중복없이 M개를 고른 모든 조합을 계산
오름차순이라서 "조합"으로 이해할 수 있음
ex) 5개의 수 -> 5C3

풀이

function solution()
{
    let n = 4
    let m = 4
    
    let arr = [];
    for (let i=1; i<=n; i++) {
        arr.push(i) // 초기 arr : 1, 2, 3, 4
    }
    let visited = new Array(n).fill(false); // 초기 visited [false, false, false, false]
    let selected = []; // vistied 스위치 역할 + arr[i] 접근을 위한 인덱스 역할
    
    let answer = [];
    
    function dfs(arr, depth, start) {
        if (depth === m) { // m이 됐으면 넣기
            let result = [];
            for (let i of selected) {
                result.push(arr[i]) // arr의 인덱스에 해당하는 값들을 넣다가 길이가 4가 됐을 때 push
                if (result.length === m) answer.push(result)
            }
        }
        
        for (let i= start; i < arr.length; i++) {
            if (visited[i]) { // visitied[i]가 true, 그 수는 빼고 진행
                continue;
            }
            selected.push(i) // 인덱스를 저장하는 공간 0 1 2 3
            visited[i] = true; // 해당하는 인덱스를 넣었으면 그 인덱스는 다시 안 넣음
            dfs(arr, depth+1, i+1) // m가 될 때까지 반복
            selected.pop() // 해당 인덱스 선택 취소 
            visited[i] = false // 해당 인덱스 방문 취소 
        }
    }
    
    dfs(arr, 0, 0)
    
    console.log(answer)
}

설명

순열 소스 코드와 다른 점은 start 변수가 사용된다는 점
조합이므로, 재귀함수를 호출 할 때 start를 넣어 start의 위치에서만 for문이 돌아가도록 하면 된다.

---