백트래킹

• 모든 경우의 수 고려할 때 사용
• 일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용
• DFS와의 차이점
  • DFS는 일반적으로 완전 탐색 목적으로, 재귀 함수를 이용해 구현
  • 백트래킹도 재귀 함수를 이용해 구현하는 것이 일반적이지만, 단순히 완전 탐색하는 것이 아니라 조건에 따라 유망한 노드로 이동

그래프 표현 방식(2가지)

1. 인접행렬

0	1	0	0
1	0	1	1
0	1	0	1
0	1	1	0

 

2. 인접리스트

0
1	2
2	1, 3, 4
3	2, 4
4	2, 3

 

 

백트래킹 기본 형태

function recursive() {
	
    if 종료 조건을 만족한다면 {
    	처리;
    }
    for 자식 노드를 하나씩 확인하며 {
    	if 임의의 조건을 만족한다면 {
        	자식 노드 방문 처리;
            재귀 함수 호출;
            자식 노드 방문 처리 해제;
        }
    }
}

 

예시) N-Queen 문제

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

• 64개의 위치에 8개의 퀸을 설치하는 모든 조합의 수는 Combination(64, 8) → 각 퀸이 서로 공격 가능한지 검사하는 방식을 사용하면 경우의 수가 매우 커짐
• 완전 탐색을 하더라도 유망한 경우에서만 탐색 가능하도록 구현

1. N개의 퀸을 놓기 위해서는 각 행마다 1개씩의 퀸을 놓아야 함 → 2²⁴
2. 트리 혹은 그래프 구조로 표현하면 다른 퀸을 놓을 위치 고려해서 이전까지 놓았던 퀸들과 상충되지 않는 조건을 만족하는 위치에 대해서만 재귀 함수 호출

const n = 0; // 체스판 크기 행
const queens = []; // 현재 체스판에 놓은 퀸의 위치 정보들

// (x, y) 위치에 퀸 놓을 수 있는지 확인
function possible(x, y) {
    // 현재까지 놓았던 모든 퀸의 위치 하나씩 확인
    for (const [a, b] of queens) {
        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; // 퀸 N개를 배치할 수 있는 경우 카운트 증가
    for (let i = 0; i < n; i++) {
        if (!possible(row, i)) continue; // 현재 위치에 놓을 수 없다면 무시
        queens.push([row, i]); // 현재 위치에 퀸 놓기
        dfs(row + 1); // 재귀 함수 호출
        queens.pop(); // 현재 위치에서 퀸 제거
    }
}