[알고리즘] 백트래킹 - 백준 단계별로 풀어보기

들어가며

이번 챕터는 백트래킹입니다. 특별한 개념은 아니고, 재귀 함수의 콜스택을 이용하여 모든 경우의 수를 탐색하는 알고리즘 입니다.

---

백트래킹

• 재귀 함수를 이용하여 제약 조건 내 모든 경우의 수를 시뮬레이션하는 알고리즘입니다.
• 제약 조건을 잘 설정하는 것이 관건입니다.
• 당연한 얘기지만 재귀 함수를 이용합니다.

알고리즘의 구조

def backtracking(매개 변수):
    if 탈출조건:
    	# 탈출 실행
    
    if 제약범위안:
    	# 실행
        # 다음 단계로
        # 실행 취소
    
    return Any # return의 이용 여부는 사용자에게 달려있음

 

 

예시

백트래킹 알고리즘은 미로 찾기와 같이 시뮬레이션이 필요한 문제를 푸는데 많이 사용됩니다.

보통 다음의 형태로 많이 사용됩니다.

int backtracking(int col){
    int cnt=0;
    if(col<=0){ // 탈출 조건
        return 1;
    }
    for(int i=1; i<=N; i++){
        if(!row[i] && !slope[i+col] && !dslope[15+col-i]){ // 제약 조건
            row[i] = slope[i+col]=dslope[15+col-i]=true; // 실행
            cnt += backtracking(col-1); // 다음 단계로
            row[i] = slope[i+col]=dslope[15+col-i]=false; // 실행 취소
        }
    }

    return cnt;
}