DFS 문제 풀이를 보다 보면 dfs로 탐색을 하다가 탐색이 끝나면 방문 했던 노드나, 값을 취소하는 코드가 있는데
예를 들어 아래 코드의 경우 울타리를 세울수 있는 경우 울타리를 세우고 dfs 탐색을 한 다음 끝나면 울타리를 제거하고 for 문을 계속 돌아준다.
나는 지금까지 책 풀이를 볼 때 이런 경우 백트래킹이라고 딱히 명시를 안해줘서 이런 경우는 그냥 이렇게 풀어야 되는구나로 알고 있었는데 이런 풀이가 백 트래킹이란 것을 오늘 알았다.
백트래킹이란?
해결책을 구하기 위해, 후보군을 구하다가, 해당 후보군이 문제의 조건을 만족하지 않으면, 다시 이전의 상태로 돌아가 다른 후보군을 찾는 기법이다.
map에서 빈 곳일때(0) 울타리를 세우는(1) 과정이다. dfs 탐색을 하여 해당 함수가 끝나면 울타리를 제거 후 계속 for 문을 돌아 답을 찾아간다.
if (map[i][j] === 0) {
map[i][j] = 1;
dfs(count + 1);
map[i][j] = 0;
}대표적인 예로는
N-Queen 문제를 들수 있는데 아래 그림 처럼 퀸들끼리 서로 공격하지 못하는 공간에 두는 것이다.
코드를 보면 쉽게 알 수 있을 것이다.
솔직히 지금에서야 이해가능 하지 내가 처음에 이런 풀이를 보면 이해 못했다.
const n = 8;
const queens = [];
function possible(x, y) {
for (let [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; // 퀸을 다 놓으면 갯수 증가
for (let i = 0; i < n; i++) {
if (!possible(row, i)) continue; // 현재 위치에 놓을 수 없다면 무시
queens.push([row, i]); // 현재 위치에 퀸을 놓기
dfs(row + 1);
queens.pop(); // 현재 위치 퀸을 제거 후에 다른 자리 탐색
}
}
dfs(0);
console.log(cnt);게임으로 예를 들어보면
4개의 엔딩을 볼 수 있는 길이 있는데 각 엔딩을 보는 경우라 생각하면 된다. (단 엔딩을 보면 게임이 끝남 다른 엔딩을 보려면 처음 부터 다시해야됨) 하지만 저장을 해두면 언제든지 그 시점에서 플레이를 할 수 있음 이제 시작하면
일단 1번째 엔딩을 보기전에 저장을 하여 내가 죽어도 저장 지점에서 선택할 수 있게 해둔 후에 1번 엔딩을 확인하러 가면 된다. 하지만 1번을 봤더니 bad 엔딩이였다. 결과를 확인했으니 저장해둔 지점에 가서 2번 엔딩을 보면 된다. 이런 식으로 결과를 확인 후 저장 시점으로 가서 다음 결과를 확인하는 방식을 백트래킹이라고 봐도 된다.
dfs는 막막했는데 길이 보이길 시작했다.