🔙 백트래킹
🤔 글을 들어가며
알고리즘 공부를 하다보면 백트래킹이라는 개념이 나온다. 문제의 효율성을 높이기 위해서 백트래킹 기법을 사용하여 탐색을 진행해야한다. 왜 백트래킹을 사용하면 효율성을 높일 수 있는지 백트래킹 예제를 보며 공부해보고자 한다.
🚩 백트래킹이란
모든 조합의 수를 살펴보는 것인데, 단 조건이 만족할 때만 탐색한다.
모든 경우의 수를 찾는 것 보다 제한 상황을 걸어 해당 조건을 만족하지 않으면 더 이상 탐색을 진행하지 않는다.
즉 조건이 만족하는 경우를 찾아야 하는 문제에서 백트래킹을 적용해서 해결할 수 있다.
백트래킹을 사용하지 않는 경우
만약 정렬되어 있지 않는 숫자 배열에서 특정 숫자를 찾아야 하는 경우는 O(n)의 시간 복잡도를 가진다.
이 경우에서는 하나씩 살펴볼 수 밖에 없으므로 백트래킹을 적용할 수 없다.
👸🏻 N-Queens 문제
백트래킹으로 해결할 수 있는 대표적인 문제인 'N-Queens'을 예제로 개념을 공부해보자.
leetcode 문제 링크 N-Qeens
문제
N * N 체스판에 N개의 Queen을 서로 공격할 수 없도록 올려놓아야 한다.
Queen은 자신을 기준으로 가로, 세로, 대각선 방향을 공격할 수 있다.
즉, Queen이 가로 세로 대각선 방향으로 존재하지 않도록 올려야한다.
모든 경우의 수를 구한다면
모든 경우를 구한다면 N * N 체스판에 N개의 Queen을 올려놓는 경우의 수를 계산해야 한다.
Queen은 한 행당 하나만 둘 수 있으므로, N행중 Queen이 올라갈 열을 찾아야 한다.
즉, N ^ N 개의 경우의 수가 나온다. 따라서 시간복잡도는 O(N^N)가 된다.
백트래킹을 사용하면
한 행당 하나의 퀸만 들어가므로, 행당 한번 퀸이 어떤 위치에 올릴지 선택한다.
만약 대각선 방향과 열방향으로 퀸이 존재한다면 해당 탐색은 멈추고, 이전 탐색으로 되돌아가서 진행한다.
따라서 모든 경우를 탐색하는 방법보다 효율성이 좋다.
즉 정리하면 다음과 같다.
- DFS를 통해 행당 하나의 퀸을 올린다. 행당 퀸이 올라간 열의 정보는
queens배열에 저장한다. 올리기 전에 올라갈 수 있는지 확인해야 한다. - isValid함수로 대각선, 열에 퀸이 존재하는지 확인한다. 존재한다면 해당 탐색을 더이상 진행하지 않는다. 이전 탐색으로 돌아가서 탐색을 진행한다.
queens의 길이가 N이라면 해당 탐색은 종료한다.qeensPos배열에queens배열을 저장하고, 이전 탐색으로 돌아가서 탐색을 진행한다.
그림으로 예시
다음과 같이 4 x 4 체스판에서 (0,0)에 퀸을 올린 경우 흰색 칸에 퀸을 올릴 수 있다.
만약 아래와 같이 (1,2)에 퀸을 올리면 퀸이 올라갈 수 있는 자리는 하나만 남게 된다. 4개를 올릴 수 없으므로 탐색을 종료하고 이전 탐색 단계로 진행한다.
(1,3)에 퀸을 올리면 퀸을 아래와 같이 3개만 올릴 수 있다. 4개를 올릴 수 없으므로 탐색을 종료하고 이전 탐색 단계를 진행한다.
이런식으로 탐색을 진행하다 보면 4 x 4 체스판에선 다음과 같은 경우가 답이 된다.
백트래킹 solution code
자바스크립트로 해결한 코드는 다음과 같다.
const solveNQueens = n => {
const board = Array(n)
.fill()
.map(() => Array(n).fill(0));
const queensPos = [];
const queens = [];
// 대각선, 열에 퀸이 존재하지 않는다면 탐색을 진행함
const DFS = L => {
if (queens.length === n) {
queensPos.push(queens.slice());
return;
} else {
// 행당 하나의 퀸만 올라감
for (let i = 0; i < n; i++) {
if (isValid(L, i)) {
board[L][i] = 1;
queens.push(i);
DFS(L + 1);
board[L][i] = 0;
queens.pop();
}
}
}
};
// 대각선, 열에 퀸이 존재하는지 확인함
const isValid = (x, y) => {
// 같은 열에 퀸 존재하는지 확인
for (let i = 0; i < x; i++) {
if (board[i][y]) return false;
}
// \ 대각선에 퀸 존재하는지 확인
for (let i = 1; ; i++) {
if (x - i < 0 || y - i < 0) break;
if (board[x - i][y - i]) return false;
}
// / 대각선에 퀸 존재하는지 확인
for (let i = 1; ; i++) {
if (x - i < 0 || y + i >= n) break;
if (board[x - i][y + i]) return false;
}
return true;
};
const createStringAnswer = () => {
const answer = [];
for (const queens of queensPos) {
const temp = [];
for (const pos of queens) {
const str = '.'.repeat(pos) + 'Q' + '.'.repeat(n - pos - 1);
temp.push(str);
}
answer.push(temp);
}
return answer;
};
DFS(0);
return createStringAnswer();
};참고 링크
https://chanhuiseok.github.io/posts/baek-1/
https://jeongdowon.medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-backtracking-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-13492b18bfa1
