백 트래킹 (Backtracking) 이란?

1. 백 트래킹 (Backtracking)

• 백트래킹 (Backtracking) 또는 퇴각 검색 (Backtrack)으로 불린다.
• 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략
  • 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보를 체크하지 않을 것을 표기)하고, 바로 다른 후보로 넘어가며, 결국 최적의 해를 찾는 방법
• 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보)를 상태공간트리(State Space Tree)를 통해 표현
  • 각 후보를 DFS 방식으로 확인
  • 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
    • Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
    • Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법

즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리(나무)에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버림 (Pruning)

 

 

상태 공간 트리 (State Space Tree)

• 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리

 

출처 : FastCampus Algorithm Lecture 

 

예를들어 a를 시작으로 각 높이의 1개 노드를 연결해 연속 4개를 홀수를 만들고 싶다고 가정하자. a - b - e - h가 전부 홀수라면 가능한 경우이다. 그런데 만약 b가 홀수가 아니라면 이미 a - b 다음에 뭐가 오더라도 조건을 만족하지 못하기 때문에 b 아래는 조사하지 않고 Backtracking 한다는 것이다. 백트래킹으로 유명한 N-Queen문제를 보면서 이해해보자.

 

 

 

2. N Queen 문제 이해

• 대표적인 백트래킹 문제
• NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제
• 퀸은 다음과 같이 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야 함

 

출처 : FastCapus Algorithm Lecture 

체스판을 N x N 체스판을 생각해보자. 퀸은 대각선, 상하좌우를 다 이동할 수 있다. 따라서 4 x 4의 체스판이라면 위와 서로 공격할 수 없는 상태로 만드려면 위와 같이 배치를 해야 한다. 

 

 

 

Pruning (가지치기) for N Queen 문제

• 한 행에는 하나의 퀸 밖에 위치할 수 없다. (퀸은 수평 이동이 가능하기 때문이다.)
• 맨 위에 있는 행부터 퀸을 배치하고, 다음 행에 해당 퀸이 이동할 수 없는 위치를 찾아 퀸을 배치한다.
• 만약 앞선 행에 배치한 퀸으로 인해, 다음 행에 해당 퀸들이 이동할 수 없는 위치가 없을 경우에는, 더 이상 퀸을 배치하지 않고, 이전 행의 퀸의 배치를 바꿈
  • 즉, 맨 위의 행부터 전체 행까지 퀸의 배치가 가능한 경우의 수를 상태 공간 트리 형태로 만든 후, 각 경우를 맨 위의 행부터 DFS 방식으로 접근, 해당 경우가 진행이 어려울 경우, 더 이상 진행하지 않고, 다른 경우를 체크하는 방식

 

예를들어 4 x 4 체스판(1행 ~ 4행, 1열 ~ 4열)에서 가장 먼저 1행 1열에 퀸을 놓았다고 생각해보자. 그러면 2행1열과 2행 2열은 놓을 수가 없다.(2행 1열은 같은 열이고, 2행2열은 대각선이기 때문) 따라서 2행에서 1열을 놓고 그 다음인 3행과 4행을 볼 필요가 없다 (왜냐하면 2행이 이미 놓을 수 없는 곳이기 때문이다) 이렇게 위의 과정을 반복해서 경우의 수를 찾으면 된다.

 

 

출처 : FastCampus Algorithm Lecture

위의 말이 이해가 되지 않는다면 이렇게 상태공간트리를 보면 이해가 될 것이다. 맨 처음에 (0, 1)을 놓았다면

(1, 0), (1, 1), (1, 2)는 놓을 수 없기 때문에 그 밑에 서브트리는 확인할 필요가 없고 (1, 3)을 시작으로 하는 것만 찾으면 된다. 

 

 

 

Promising for N Queen 문제

• 해당 루트가 조건에 맞는지를 검사하는 기법을 활용하여,
• 현재까지 앞선 행에서 배치한 퀸이 이동할 수 없는 위치가 있는지를 다음과 같은 조건으로 확인
  • 한 행에 어차피 하나의 퀸만 배치 가능하므로 수평 체크는 별도로 필요하지 않음

 

출처 : FastCampus Algorithm Lecture 

위의 개념을 알고 있어야 코드를 구현하는데 많은 도움이 된다. 퀸을 현재 자리에 놓을 수 있는지 없는지를 체크하는 과정이다. 수직체크는 같은 열인지 확인하는 것이기 때문에 열끼리 뺀 것의 절대값이 1이라면 같은 열이다.

그리고 대각선체크는 행끼리 뺀 값 == 열끼리 뺀 값이 성립한다면 대각선의 위치이기 때문에 놓을 수 없다. 

 

 

 

 

코드 구현 with Java

import java.util.Scanner;
 
public class NQueen {
    public static int N;
    public static int count;
 
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        N = input.nextInt();
 
        for (int i = 1; i <= N; ++i) {
            int[] col = new int[N + 1];
 
            // 인덱스 0은 쓰지 않음
            col[1] = i;   // N x N 체스판에서 1행1열 ~ 1행 N열 까지 하나 씩 놓으면서 경우의 수 구하기
            dfs(col, 1);
 
        }
        System.out.println(count);
    }
 
    public static void dfs(int[] col, int row) {
        if (row == N) {
            count++;    // 1행 1열 ~ 1행 N열 까지 놓을 때 가능한 경우의 수 전부 count
        } else {
            for (int i = 1; i <= N; ++i) {
            col[row + 1] = i;   // col[행] = 열 으로 생각 (ex : col[2] = 1 이라면 2행 1열 이라는 뜻)
            if (isPossible(col, row + 1)) {
                dfs(col, row + 1);
            }
        }
    }
 
    }
 
    public static boolean isPossible(int[] col, int row) {
        // 현재 메소드에서 체스를 놓은 행 다음 행에서 놓을 수 있는 자리를 판별해준다.
        for (int i = 1; i < row; ++i) {
            if (col[i] == col[row]) return false; // 같은 열 이면 놓을 수 없기 때문에 false
 
            if (Math.abs(i - row) == Math.abs(col[i] - col[row])) return false;
            // 대각선을 판별하는 조건은 행끼리 빼기 ==
        }
 
        return true; // 대각선도 아니고 같은 열도 아니라면 true
    }
}
 

 

 

 

 

[강의자료 출처]

 

https://www.fastcampus.co.kr/dev_online_algo/

[올인원 패키지] 알고리즘/기술면접 완전 정복 Online | 패스트캠퍼스