ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백 트래킹 (Backtracking) 이란?
    Computer Science/Algorithm 2020. 1. 30. 14:21
    728x90
    반응형

    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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    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 | 패스트캠퍼스

    실무 강의 위주로 강의 콘텐츠를 제공하던 패스트캠퍼스가 특별히 기획부터 강의 촬영까지 오직 취업만을 목표로 만든 강의입니다. 국내 100대 기업의 개발자 취업 프로세스를 분석하고, 코딩테스트 기출문제, 빈출문제를 살펴서 취업에 정말 중요한 개념 위주로 단기간에 학습할 수 있도록 강의를 구성했습니다. 일반적인 자료구조/알고리즘 학습 강의와는 방향성이 다릅니다.

    www.fastcampus.co.kr

     

    반응형

    댓글

Designed by Tistory.