백트래킹...! N Q문제

재귀 알고리즘 공부하다가 이해가 안되는 부분이 생겨서 파고 들다 백트래킹이란 개념이 나왔다.

 

그래서 알아보는 백트래킹이란 ...!

• 재귀적으로 문제를 하나씩 탐색해 가면서, 현재 재귀를 통해 확인 중인 상태가 제한된 조건을 만족하는지 판별하고, 만약에 만족하지 않는다면 다시 이전 상태로 돌아가는 것을 말한다 ..! 이렇게 탐색할 필요가 없는 상태를 제외하는 것을 ..한정(bounding)조작이라고 하고.. 분기 조작과 한정 조작을 조합하여 문제를 풀어 가는 방법을 분기 한정법(branching and bounding method) 라고 한다 ..!
• 백트래킹을 사용하는 알고리즘 중 하나가 DFS이다.. 

아하! 결국 아래의 문제에서

flag_a[j]=flag_b[i+j]=flag_c[i-j+7]=false;

이 부분이 백트래킹에 해당한다 . 먼저 set(i+1)에서 실패를 했다면 그전으로 돌아가 해당 경로로 들어가는 길을  막고 다시 탐색~.. 

아마 이런식으로 모든 0~n-1 인덱스를 만족하는 값을 찾기 위한 탐색을 과정을 수행할 것이다

 

---

<3월 17일 추가>
파이썬으로 다시풀어보다가 전에 내가 썻던 설명이 이해가 안되서 다시 차근차근 풀어봤다.

대략 적인 내가 생각하는 슈도코드임..!

즉 .. 마킹자리를 예정해서 재귀를 돌리고 그 마킹자리가 맞는지 아닌지 for(j->인덱스끝까지)돌리면서 확인한다..!

파이썬으로 푼 백준 9663 N-Queen 문제이다.

# 체크의 개념으로 푼다
import sys

# 체크의 개념으로 풀지만 일단 봐봐 n을받아야지 ?

n = int(sys.stdin.readline().strip())

# 마킹용 배열을 생성해서 해봐
# 인덱스 번호로 하는걸기억 ..... !
h=[True]*(n)
rl=[True]*(2*n-1) # / 방향 i+j
lr=[True]*(2*n-1) # \ 방향 n-1+i-j

global count
count=0
def set_i(i:int,n:int)->int:
    for j in range(n):
        if h[j] and rl[i+j] and lr[n-1-j+i]:
            if i==(n-1) :
                global count
                count+=1
            else: # i마킹이 끝난게 아니라면! 마킹하러 가세요
                h[j],rl[i+j],lr[n-1-j+i]=False,False,False # 퀸 예상자리 .
                set_i(i+1,n)
                h[j], rl[i + j], lr[n - 1 - j + i] = True, True,True

    return count

print(set_i(0,n))

 

package 구현.자바알고리즘.재귀알고리즘;

public class EightQueen {
    //각 행에 퀸을 배치했는지 체크
    static boolean[] flag_a = new boolean[8];
    //  '/' 대각선 방향으로 퀸을 배치했는지 체크
    static boolean[] flag_b = new boolean[15];
    // '\' 대각선 방향으로 퀸을 배치했는지 체크
    static boolean[] flag_c = new boolean[15];
    // 각 열에 있는 퀸의 위치를 출력
    static int[] pos = new int[8];

    static void print(){
        for(int i =0;i<8;i++){
            System.out.printf("%d",pos[i]);
        }
        System.out.println();
    }

    //i열의 알맞은 위치에 퀸을 배치
    static void set(int i){
        for(int j=0;j<8;j++){
            if(!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7]){
                //퀸을 j행에 배치
                pos[i]=j;
                if(i==7) print();
                else {
                    flag_a[j]=flag_b[i+j]=flag_c[i-j+7]=true;
                    set(i+1);
                    // 백트레킹의 개념이다 ...
                    // 
                    flag_a[j]=flag_b[i+j]=flag_c[i-j+7]=false;
                }

            }
        }
    }

    public static void main(String[] args) {
        set(0);
    }
}