c++ 백 트래킹

DFS + 최적화 기법

DFS를 진행하면서 답이 되지 않을 경우의 수일 경우 해당 루트는 진행을 종료하여 연산 횟수를 줄임. 

 

즉, DFS 한번 진행 할 때 마다 해당 루트가 유효한지 check promising을 진행하여 false 일 경우 진행안함.

[DFS 함수 + check promising 함수]

 

 

활용 예제 [ N-Queen]

체스판 M x M 에서 M 개의 Queen들이 서로 공격할 수 없는 곳에 배치될 경우의 수를 구하는 문제.

(Queen은 수직, 수평, 대각선 으로 공격 가능)

	Q
			Q
Q
		Q
				Q

 

[공략]

1. 1차원 int 배열을 일단 준비. ( 배열의 index = 행, value = 열.   //각 행당 queen이 배치될 위치)

2. 한 행당 하나씩만 배치하는 것으로 DFS 진행.  (수평 공격 가능하기 때문)

3. 현재 장소에 배치할 경우 유효한지 확인. (promising 진행)
   3-1. [같은 열] 이거나 [행 차이 = 열 차이] 면 false

• if( queen[i] == queen[j] || i-j == queen[i] - queen[j] )

4. 유효한 경우에만 해당 루트 진행.

5. M개의 queen이 다 배치된 경우, result++.

 

 

bool PromiseCheck(int table[], int M, int raw, int colm)
{
    //i = 과거 행
    for (int i = 0; i < raw; ++i)
    {
        if (table[i] == colm || (raw - i) == abs(colm - table[i]))
            return false;
    }
    return true;
}

void NQueen(int table[], int M,  int start, int end, int& result)
{
    if (start >= end)
    {
        ++result;
    }
    else
    {
        //열 고르기
        for (int i = 0; i < M; ++i)
        {
            if (PromiseCheck(table, M, start, i))
            {
                table[start] = i;
                NQueen(table, M, start + 1, end, result);
            }

        }
    }
}

void main()
{
    //체스판 N x N 에서 N 개의 Queen들이 서로 공격할 수 없는 곳에 배치될 경우의 수를 구하는 문제.
    constexpr int N = 15;
    int table[N] = { 0, };  // index = 행, value = 열
    int answer = 0;

    NQueen(table, N, 0, N, answer);

    cout << "N=15, NQueen 경우의 수 : " << answer << endl;
}