[알고리즘] 되추적(Backtracking)

'백트래킹' 이라는 단어 하면 왠지 어려울 것 같은 느낌과 거부감이 들지만
알고보니 미로찾기 도중 길이 막히면 되돌아가는 알고리즘인 셈이다.

풀이 방법

• DFS의 응용

• 재귀함수 혹은 스택으로 풀이

• promising한지(다음 단계에서 해가 나올 싹이 있는지)를 찾아내는 function을 구현하는 것이 핵심

N-Queens 알고리즘

N*N의 체스판에서 N개의 체스를 서로 대각선 혹은 수직으로 연결되지 않도록 놓는 알고리즘

조건 수행 방법

i. 같은 열을 체크
col[i]를 선언하고 i번째 행(row)에서의 열의 위치를 저장
즉, 체스판의 i번째 줄에서 몇번째 칸에 체스를 놓았는지 저장

if (col[i] == col[k]) non-promising

ii. 대각선 체크
열 번호의 차와 행 번호의 차가 절댓값이 같으면 대각선에 놓인 것

if ( abs(col[i]-col[k]) == abs(i-k) )

Python 풀이

n = 4
col = [0] * (n + 1)
n_queens(col, 0)

# n-Queens
def n_queens(i, col):
	n = len(col) - 1
    if (promising(i, col)):
    	if(i == n):
        	print(col[1:n+1])
        else:
        	for j in range(1, n+1):
          		col[i + 1] = j
                n_queens(i + 1, col)

# 유망함수
def promising (i, col):
	k=1
    flag = True
    while (k < i and flag):
    	if (col[i] == col[k] or abs(col[i] - col[k]) == (i - k) ):
        	flag = False
        k+=1
    return flag

C++ 풀이

#include <stdio.h>
#include <cstdlib>
#include <iostream>

using namespace std;

int N;
int cnt = 0;

void N_Queens(int col[], int i);
bool promising(int col[], int i);

int main(){
    int col[16] = {0};
    cin >> N;
    N_Queens(col, 1);
    cout << cnt;
    return 0;
}

void N_Queens(int col[], int i){
    for (int k = 1; k <= N; k++){
        col[i] = k;
       
        if (promising(col, i)){
            if (i == N) ++cnt;
            else N_Queens(col, i + 1);
        }
    }
}

bool promising(int col[], int i){
    for (int k=1; k<i; k++){
        if (col[k] == col[i] || abs(col[k] - col[i]) == abs(k - i)){
            return false;
        }
    }
    return true;
}

참고 영상: https://www.youtube.com/watch?v=z4wKvYdd6wM