[2023-10-02] TIL - 백트래킹

백트래킹

- 모든 경우의 수를 탐색하는 알고리즘

자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다.
탐색에서 순환이 발생할 수 있다면 BFS를 이용하는 것이 편하다.

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

📋풀이방법

1. 체스가 한행에 하나의 퀸만 들어갈 수 있다는 것을 알아야한다

2. 그리고 다음 행에 퀸을 어디에 둘지 재귀로 검사하면서 백트래킹을 이용해야한다.

3. 위 그림처럼 둘 수 없는 좌표는 뻗어나갈 수 없게 재귀를 멈춰줘야한다.

 

 

내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let N=Number(input.shift());
let count=0;
let board=Array(15).fill(0)
function check(idx){
    for(let i=0;i<idx;i++){
        //board[idx]==board[i] : 같은 열에 위치했는지
        //idx-i==Math.abs(board[idx]-board[i]) : 같은 대각선에 위치했는지
        if(board[idx]==board[i] || idx-i==Math.abs(board[idx]-board[i])){
            return 0;
        }
    }
    return 1;
}

function DFS(idx){
    if(idx==N){
        //모든 행에 퀸을 두었다면
        count++;
        return;
    }

    else {
        for(var i=0;i<N;i++){
            board[idx]=i;
            //check함수로 백트래킹을 해 가지치기를 한다.
            if(check(idx)){
                //만약 백트래킹에 걸리지않는다면 다음 행으로 넘어가 퀸을 둔다.
                DFS(idx+1);
            }
        }
    }
} 
DFS(0);
console.log(count);

 

 

💢어려웠던 점

1. 퀸이 한 행에 하나의 퀸만 존재한다는 당연한 조건을 생각하지 못햇다.

-> 이 조건이 코드를 더간단하게 한다.

 

2. 2차원배열이아닌 1차원 배열만으로 가능하다

-> 위 조건에서 한행에는 하나의 퀸이 존재하므로 배열의 인덱스에 퀸의 열 번호를 표시하면 1차원 배열로 가능하다.

3. 현재 퀸이 위치한 행열과 다음 행에 위치한 퀸이 겹치는지 확인하는 조건을 생각하지 못했다.

 - 첫 번째 조건은 현재 두었던 퀸과 이제까지 두었던 퀸의 열값이 같으면 안된다.

 - 두 번째 조건은

  | 현재 둔 퀸의 행값 - 이제까지의 퀸의 행값 | == | 현재 둔 퀸의 열값 - 이제까지의 퀸의 열값 |

 

4. BFS로는 가능하나 메모리초과가 나는 것 같다.

function solution(n) {
    var answer = 0;
    
    function check(dy,dx,board,cnt){
        for(let i = 0; i < cnt+1; i++){
            let [ty,tx]=board[i];
            if(tx==dx ||Math.abs(dx-tx) === dy-ty){
                return 0;
            } 
        }
        
        return 1;
    }
    
    
    for(let j=0;j<n;j++){
        let queue=[[0,j,1]];
        let board =Array.from({length:n},()=>[]);
        board[0]=[0,j];
        while(queue.length>0){
            let [y,x,cnt]=queue.shift();
            if(cnt==n){
                answer++;
                break;
            }
            else{
                board[cnt]=[y,x]
                for(let z=0;z<n;z++){
                    if(check(y+1,z,board,cnt)){
                        queue.push([y+1,z,cnt+1]);

                    }
                }

            }
        }
    }
    
    
    
    return answer;
}

- 위처럼 BFS로도 하려고 했지만 메모리초과가 나서 실패하는 것인지.. 제출이 안된다.