백트래킹 알고리즘(BackTracking)

백트래킹(BackTracking)

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다.

쉽게 설명해서 어떤 문제를 푸는데 있어 모든 경우의 수를 시도하여 문제의 정답을 찾아나간다.

하지만 백트래킹에서는 한정 조건 에서의 모든 경우의 수를 시도하는 것이기 때문에 실제로 상당한 경우의 수들이 배제되기 때문에 단순 다중 for문 보다는 빠르게 해결되는 경우가 많다.

---

백트래킹 구현

보통 백트래킹(BackTracking)의 구현은 BFS나 DFS와 함께 구현한다.

모든 경우의 수에서 한정 조건을 만족하는경우를 탐색하는 것이기 때문에 완전탐색기법인 BFS와 DFS가 모두 구현이 가능하다.

하지만 백트래킹의 특성에서 한정 조건에 부합하지 않다면(Node가 유망하지 않다면) 이전 수행(이전 Node)으로 돌아와야하기 때문에 BFS보다는 DFS의 구현이 더 편하다.

너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)과 백트래킹

• 깊이 우선 탐색(DFS)

DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다.

따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것이다.

• 백트래킹(Backtracking)

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다.

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다.

가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 된다.

---

백트래킹의 Key : 한정 조건

구현할 때 가장 중요한 것이 한정 조건 이다.

한정 조건을 걸어 완전탐색에서 유망하지 않은 시도를 걸러내는 것이 바로 백트래킹의 본질이다.

그럼 한정 조건이 정확히 무엇인지 어떤식으로 작동하지는 예제를 통해서 알아보도록 하자.

예제) 3X3 행렬 선택 게임

아래와 같은 행렬이 존재할 때 3개의 숫자를 선택하는 게임이다.

단, 선택한 숫자들의 행과 열은 모두 중복하면 안된다. 가장 적은 점수를 얻는 것이 승리하는 것이라 할때 선택해야하는 숫자 3개를 골라보자.

먼저 이 문제를 푸는 가장 쉬운 방법은 당연히 모든 방법을 다 해보는 것이다.

숫자 3개를 선택하는 모든 경우를 다해보는 것이 정답이지만 이 문제에서는 조건이 하나 있다.

고른 숫자는 모두 행과열이 달라야 한다는 것이다. 이것이 바로 전에 설명했던 한정 조건 이다.

이 문제에서의 한정 조건은 ‘행과열이 달라야 한다.’ 인 것이다.

먼저 이 문제를 구조화 한다면 아래와 같이 나타낼 수 있다.

위 구조화 그림은 한정 조건과 상관없이 모든 경우의 수를 나타낸 구조이다. 만약 여기서 한정 조건을 추가한다면 아래와 같은 구조가 될 것이다.

차이점이 한눈에 보이는 것을 알 수 있다. 위와 같이 한정 조건 을 적용한 뒤에 DFS 를 통해서 전체 탐색을 진행하는 것이 바로 백트래킹이다.

예제로 설명하자면 첫번째 행에서 만약 1을 택한다면 두번째 행의 숫자는 2,4,7이 존재하지만 2는 1과 같은 열이기 때문에 더 탐색하더라도 정답이 될 수 없다.

따라서 첫번째를 1을 선택하면 2는 유망하지않고 4와 7만 유망하기 때문에 4와 7만을 Node에 추가시킨다.

이러한 방식으로 가장 마지막 행까지 모두 수행하면 위와 같은 트리 구조를 얻을 수 있고 결론적으로 정답을 찾을 수 있는 것이다.

---

백트래킹 알고리즘 예시(N-Queen 문제)

💡 문제 확인

• N*N 체스 보드 위에 퀸 N개가서로 공격할 수 없게 놓는 문제

• 놓여진 퀸 자리의 같은 행, 열, 대각선에 다음 퀸을 놓지 못한다.

💡 N-Queen 문제의 해법

방법: 이전까지 놓았던 퀸들과 상충되지 않는 조건을 만족하는 위치에 대해서만 재귀 함수를 호출

1. 퀸을 모두 놓지 않은 경우에

2. 현재 행에 존재하는 열을 하나씩 확인

3. 현재 위치에 놓을 수 없다면(같은 열, 행, 대각선일 경우) 무시

4. 현재 위치에 놓을 수 있으면 놓고 재귀함수 호출

5. 현재 위치에서 퀸 제거

💡 N-Queen 문제 해결 코드

let n = 8; // 전체 맵(map)의 크기
let queens = []; // 현재 체스판에 놓인 퀸(queen)의 위치 정보들

function possible(x, y) {
  // (x, y) 위치에 퀸을 놓을 수 있는지 확인
  for (let [a, b] of queens) {
    // 현재까지 놓았던 모든 퀸(queen)의 위치를 하나씩 확인하며
    if (a == x || b == y) return false; // 행이나 열이 같다면 놓을 수 없음
    if (Math.abs(a - x) == Math.abs(b - y)) return false; // 대각선에 위치한 경우 놓을 수 없음
  }
  return true;
}

let cnt = 0;
function dfs(row) {
  if (row == n) cnt += 1; // 퀸(queen)을 N개 배치할 수 있는 경우 카운트
  for (let i = 0; i < n; i++) {
    // 현재 행(row)에 존재하는 열을 하나씩 확인하며
    if (!possible(row, i)) continue; // 현재 위치에 놓을 수 없다면 무시
    queens.push([row, i]); // 현재 위치에 퀸을 놓기
    dfs(row + 1); // 재귀 함수 호출
    queens.pop(); // 현재 위치에서 퀸을 제거하기
  }
}

dfs(0);
console.log(cnt);

---