[알고리즘] 백트래킹

|  백트래킹

- 모든 가능한 경우의 수 중에서 유망하지 않은 쪽은 제외하고 최적해를 구하는 방법

- 주로 재귀를 사용해서 구현한다.

유망(Promising)	가능성 있다.
가지치기(Pruning)	가능성 없는 것 제외하기
백트래킹(Backtracking)	유망하지 않은 쪽으로는 가지 않고 Back한다.

 

|  N-Queen 을 통한 백트래킹 이해

https://www.acmicpc.net/problem/9663

9663번: N-Queen

- N x N의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다고 할 때

- 메모리 공간 : 

(1) 각 행의 열을 짚어줄 배열

(2) 카운팅 변수

- Flow

(1) i번째 행의 각 열에 퀸을 배치한다.

(2) 유망여부 : 이전 행의 퀸 열의 상하좌우, 대각선에 해당되는가? 

- 2-1 ) YES : 다음 행으로 이동 

- 2-2 ) NO : 가지치기

(2) 모든 행을 다 돌은 경우, 방법의 수 카운팅

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    static int[] board; // 각 행의 퀸 열 위치
    static int cnt = 0; // 전체 카운트 수
    static int nQueen(int n, int r){
        // 탈출문
        if (r == n) {
            cnt++;
            //System.out.println(Arrays.toString(board));
            return cnt;
        }

        // 구현문
        // r번째 행에 대하여
        for (int i = 0; i < n; i++) {
            // 열 위치값 지정
            board[r] = i;

            // promising
            if (isPromising(r, i)){
                nQueen(n, r + 1);
            }
        }

        return cnt;
    }

    static boolean isPromising(int r, int c) {
        // 현재 행 전까지 겹치는 부분 확인
        for (int i = 0; i < r; i++) {
            int pre_r = i;
            int pre_c = board[i];

            if (pre_c == c || r - pre_r == Math.abs(c - pre_c)){
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        board = new int[N];

        System.out.println(nQueen(N, 0));
    }
}

 

|  그 외에 백트래킹을 사용하는 예시

(1) Permutation(순열)을 구하는 알고리즘 

import java.util.Arrays;

public class Practice {

    // 순열
    static int cnt = 0;
    static boolean[] visited;
    static int[] out;
    static int solution(int[] arr, int n, int r) {
        visited = new boolean[n];
        out = new int[r];

        return permutation(arr, n, r, 0);
    }

    static int permutation(int[] arr, int n, int r, int depth){
        if (depth == r){
            cnt++;
            System.out.println(Arrays.toString(out));
            return cnt;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, n, r, depth + 1);
                out[depth] = 0;
                visited[i] = false;
            }
        }

        return cnt;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3 };
        int n = 3; // n개의 수 중에
        int r = 2; // r개의 수를 고르는 방법
        System.out.println(solution(arr, n, r));
    }
}

(2) N자리수에서 앞자리부터 일의 자리수, 십의 자리수... N의 자리수가 모두 소수인 수를 찾는 알고리즘

- 첫번째 자릿수는 무조건 2,3,5,7중 하나가 들어가야한다.

- 두번재 자릿수부터 0 ~ 9 중에 유망한 수를 구한다.

  > 유망하다 : 2나 5로 나누어떨어지지 않는 수

     > 백트래킹 : 현재까지 자릿수의 숫자(ex.233)가 소수인지 확인

  > 유망하지X : 가지치기 

public class Practice2 {

    static void solution(int n) {
        // 첫번째 자릿수는 무조건 2, 3, 5, 7 중 하나
        int[] primes = {2, 3, 5, 7};

        for (int i = 0; i < primes.length; i++) {
            getPrimes(primes[i], n,1);
        }
    }

    static void getPrimes(int prime, int n, int digitLen){
        
        if (digitLen >= n){
            System.out.print(prime + " ");
            return;
        }

        // 두번째 자릿수부터는 0 - 9중에
        for (int i = 0; i < 10; i++) {
            // 가지치기 : 2 또는 5로 나누어떨어지지 않는 수
            if (i % 2 != 0 && i % 5 != 0) {
                int primeCandidate = 10 * prime + i;

                // backtracking : 소수이면
                if (isPrime(primeCandidate)){
                    getPrimes(primeCandidate, n,digitLen + 1);
                }
            }
        }
    }
    
    static boolean isPrime(int n) {

        if (n < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 3;
        solution(n);
    }
}

 

|  백준 문제집

https://www.acmicpc.net/step/34

백트래킹 단계

 

[ 출처 및 참조 ]

부트캠프 수업 후 정리한 내용입니다.