백트래킹
백트래킹은 모든 경우의 수를 탐색하는 알고리즘 입니다.
DFS나 BFS를 이용할 수 있고 탐색에서 사이클이 발생할 수 있다면 BFS를 이용하는 것이 편합니다.
모든 경우의 수를 탐색하기 때문에 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 가지치기(Pruning)과정을 거칩니다. 자바스크립트의 재귀호출은 효율이 나쁘기 때문에 DFS를 구현할때
스택을 이용하는 것이 좋습니다.
작성법
그럼 어떻게 작성해야 할까요?
- 먼저 모든 경우의 수를 찾을 수 있도록 코딩을 합니다.
- 이후 문제에서
특정 조건을 만족하는 것만 탐색을 진행하고 나머지는 탐색하지 않도록 조건문을 작성합니다. - 즉, 절대로 답이 될 수 없는 것은 탐색을 종료합니다.
N-Queen 문제
백트래킹의 대표적인 문제인 N-Queen 문제입니다.
문제
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
제한사항
퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
n은 12이하의 자연수 입니다.
풀이
먼저 가지치기를 진행해보면
1. 퀸을 둔 행은 퀸이 존재할 수 없다.
2. 퀸을 둔 열은 퀸이 존재할 수 없다.
3. 퀸을 둔 대각선 왼쪽/오른쪽은 퀸이 존재할 수 없다.
2차원 배열로 진행하게되면 성능이 크게 떨어지기때문에 1차원 배열을 사용하면
table[0] = 1은 체스판 위에서 첫번째에 두번째 칸에 해당합니다.(1번 그림의 퀸 위치)
- 같은 인덱스에 여러 값이 들어갈 수 없기때문에 행이 자연스럽게 가지치기 됩니다.
- 인덱스가 같으면 가지치기 합니다.
- 0부터 시작하고,
table[0] = 1,table[2] = 3일때 행의 차이 abs(0 - 2)와
abs(1 - 3) 이 같기때문에 대각선에 존재하여 가지치기 합니다.
퀸을 둘 수 있는지 확인 여부에 대한 함수를 작성합니다.
function check(table, row) {
// 이전에 두었던 퀸의 위치 확인
for (let i = 0; i < row; i++) {
// 행의 위치와 대각선의 위치 확인
if (table[i] === table[row] || Math.abs(table[i] - table[row]) === Math.abs(i - row)) {
return false
}
}
return true
}매개변수로 들어온 row가 체스판의 끝에 도달하면 종료하는 플래그를 만들고,
체스판의 길이만큼 순회하면서 퀸을 놓습니다. 이때 check함수를 이용해 퀸을 둘 수 있는 위치이면 count로 추가하고 row에 1을 더한값을 호출합니다.
function search(table, row) {
const n = table.length
let count = 0
if (n === row) { // 체스판 끝에 도달
return 1 // 탈출
}
for (let col = 0; col < n; col++) {
table[row] = col // 퀸을 둔다
if (check(table, row)) { // 퀸을 둘 수 있으면
count += search(table, row + 1) // 다음행으로 이동
}
}
return count
}마지막으로 체스판을 n의 길이만큼 만들고 search함수를 호출합니다.
function solution(n) {
let table = new Array(n).fill(0) // n = 4 [0,0,0,0]
return search(table, 0)
}출처
https://school.programmers.co.kr/learn/courses/30/lessons/12952
