14주차

Backtracking

개념

✨Backtracking이란?

• 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 해를 다시 찾아가는 기법
• 재귀 기반으로, 어떤 단계에서 해가 될 수 없거나 유망하지 않으면 더 이상 진행하지 않고 초기에 탐색을 중단(가지치기)함으로써, 불필요한 연산을 줄이는 것이 핵심

✨주요 용어

• 유망함
  • 진행 중인 경로가 해답을 찾을 가능성이 있음
• 가지치기
  • 유망하지 않은 하위 트리를 잘라냄
    : 특정 조건을 만족하면 추가 탐색이 필요 없는 경우 수행

✨DFS와의 관계

DFS는 깊은 부분을 먼저 탐색하기 때문에 뒤로 돌아가야 하는 일이 발생한다
-> 이때 Backtracking 이용!

💭둘의 차이가 있다면?

• DFS : 단순한 깊이 우선 탐색
• Backtracking : 조건을 만족하지 않으면 탐색을 중단하고 되돌아가는 최적화 기법

✨구조 예시

def backtrack(상태):
    if 해답 조건 만족:
        해답 처리
    else:
        for 선택 in 가능한 선택지:
            if 선택이 유망하다면:
                상태 갱신
                backtrack(새로운 상태)
                상태 되돌리기

해당 상태가 해답 조건을 만족하면 해답 처리  
해답이 아니라면 선택 가능한 선택지를 반복  
선택지의 선택이 유망하다면 상태를 갱신하고, 갱신된 상태로 다시 탐색  
탐색이 끝나면 원상복구 (다른 선택지 탐색을 위해)

✨장단점

👍장점

• 불필요한 탐색을 줄이므로 효율적임
• 재귀 기반 구조이므로 구현이 직관적임

👎단점

• 최악의 경우 모든 해를 탐색해야 함
• 유망성 판단 기준에 따라 성능 갈림

문제 패턴

✨제약 충족 문제

• N-Queens, 스도쿠 등
• 조건을 만족해야 한다는 제약이 핵심

=> Backtracking으로 조건을 만족하지 않으면 탐색 중단

✨조합 탐색 문제

• 부분집합/조합 생성, 순열 생성 등
• 가능한 경우의 수 많음

=> 조건을 만족하지 않는 경우의 수는 미리 잘라냄

✨경로 탐색 문제

• 미로 찾기 등

=> 경로를 따라가며 조건을 만족하지 않으면 되돌아감

✨문자열/패턴 매칭 문제

=> 문자열이나 패턴을 따라가며 조건을 만족하지 않으면 탐색 중단

예시 문제 기반 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12952

Java

class Solution {
    int answer = 0;
    boolean[] col, diag1, diag2;
    int N;

    public int solution(int n) {
        N = n;
        col = new boolean[N];
        diag1 = new boolean[2*N];
        diag2 = new boolean[2*N];
        dfs(0);
        return answer;
    }

    void dfs(int row) {
        if (row == N) {
            answer++;
            return;
        }
        for (int c = 0; c < N; c++) {
            if (!col[c] && !diag1[row+c] && !diag2[row-c+N]) {
                col[c] = diag1[row+c] = diag2[row-c+N] = true;
                dfs(row+1);
                col[c] = diag1[row+c] = diag2[row-c+N] = false;
            }
        }
    }
}

Python

def solution(n):
    answer = 0
    col = [False] * n
    diag1 = [False] * (2*n)
    diag2 = [False] * (2*n)

    def dfs(row):
        nonlocal answer
        if row == n:
            answer += 1
            return
        for c in range(n):
            if not col[c] and not diag1[row+c] and not diag2[row-c+n]:
                col[c] = diag1[row+c] = diag2[row-c+n] = True
                dfs(row+1)
                col[c] = diag1[row+c] = diag2[row-c+n] = False

    dfs(0)
    return answer

JavaScript

function solution(n) {
  let answer = 0;
  let col = new Array(n).fill(false);
  let diag1 = new Array(2*n).fill(false);
  let diag2 = new Array(2*n).fill(false);

  function dfs(row) {
    if (row === n) {
      answer++;
      return;
    }
    for (let c = 0; c < n; c++) {
      if (!col[c] && !diag1[row+c] && !diag2[row-c+n]) {
        col[c] = diag1[row+c] = diag2[row-c+n] = true;
        dfs(row+1);
        col[c] = diag1[row+c] = diag2[row-c+n] = false;
      }
    }
  }

  dfs(0);
  return answer;
}

퀸은 가로, 세로, 대각선으로 움직일 수 있으므로  
1. 각 열에 퀸이 놓였는지 체크
2. 왼쪽 위 -> 오른쪽 아래 방향 대각선 체크  
3. 오른쪽 위 -> 왼쪽 아래 방향 대각선 체크
해야됨
  
각 행에서 가능한 모든 열에 퀸을 놓아봄
모든 행에 퀸을 놓았으면 경우의 수 하나 추가  
  
해당 열과 두 대각선에 퀸이 없다면 탐색  
퀸을 놓았다고 표시 후 다음 행 재귀 호출  
탐색 종료 시 놓았던 퀸 원상복구

실수 포인트

✨원상복구 안함

다음 선택지를 탐색하기 위해 탐색이 끝나면 원래 상태로 되돌려야 하는데, 이걸 하지 않아 다음 선택지 탐색에서 잘못된 결과 나옴

✨유망성 조건 잘못 설정

조건이 너무 느슨하면 불필요한 탐색이 많아져서 시간 초과, 조건이 너무 엄격하면 실제 해답 놓쳐서 오답