알고리즘 - 백트래킹

✔백트래킹(Backtracking)

• 퇴각 검색
  • 모든 조합을 시도 (해을 얻을 때 까지 모든 가능성을 시도
    • 기본은 완전 탐색에서 출발.
    • 불가능한 경우를 버리면서 진행.
  • 모든 가능성은 하나의 트리로 구성 가능.
    • 여러 가지 중 알맞은 가지를 선택해 새로운 선택지 생성.
    • 선택지들을 선택해가며 해가 될 수 있는지 판단.
    • 반복을 통해 최종 상태 도달.
    • 보통 재귀 함수로 구현

◾해 구하기

• 루트 노드에서 리프 노드까지의 경로 => 해답 후보(Candidate Solution)
  • 기본 : 완전 탐색을 통해 해답을 찾음.
    • 해답이 될 가능성이 없는 노드의 후손 노드들도 모두 검색하므로 비효율적.
  • 백트래킹 기법 : 가지치기를 통해 효율성 상승.
    • 노드의 유망성 을 점검한 후 유망(Promising)하지 않다고 결정되면 부모 노드로 돌아가(Backtracking) 다음 자식 노드 점검.
    • 유망하다(Promising) : 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 가능성이 있음을 의미.
    • 가지치기(Pruning) : 유망하지 않은 노드가 포함되는 경로는 더이상 고려하지 않는 것.
• 백트래킹과 완전 탐색(DFS)의 차이
  • 가지치기 를 통해 불필요한 경로 조기에 차단.
  • 하지만, 백트래킹도 최악의 경우에 지수 함수(Exponential Time)을 요하므로 처리 불가능일 수 있음.

◾백트래킹 알고리즘

• 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 것.
• 유망하지 않다면 가지치기하여 더이상 해당 경로를 탐색하지 않음
• 주로, DFS로 모든 경우의 수를 탐색하는 과정에 조건을 통해 진행 방식 결정.

• 알고리즘 절차

1. 상태 공간 트리의 깊이 우선 검색(DFS) 실시.
2. 각 노드가 유망한지 점검.
3. 만일 그 노드가 유망하지 않다면, 부모 노드로 돌아가 다른 노드 계속 검색.

1. N-Queen 문제

• 크기가 N x N 인 체스판 위에 퀸 N 개가 서로를 공격 할 수 없게 놓는 경우의 수를 구하는 문제.
  • 퀸과 같은 행, 같은 열, 대각선 위치에 존재하면 퀸이 공격할 수 있음.
  • 따라서 N개의 퀸이 모두 같은 행, 같은 열, 대각선 위치에 없게되는 경우를 탐색하는 것.

import java.util.Scanner;

public class NQueenTest {
	static int N, cols[], ans;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		ans = 0;
		cols = new int[N+1];
		
		setQueen(1);
		System.out.println(ans);
	}
	
    // 파라미터 행에서 퀸의 위치를 설정하는 함수.
    // - 정답을 찾았다면 종료.
    // - 1 ~ N 인덱스를 차례로 넣으며 탐색.
    // - 유망한 노드이면 다음 행 검색.
    // - 유망하지 않다면 패스.
	public static void setQueen(int row) {
		
		if (row > N) {
			ans++;
			return;
		}
		
		for(int i = 1; i <= N; i++) {
			cols[row] = i;
            // 해당 위치에 퀸을 놓을 수 있다면 다음 행 탐색.
			if(isAvailable(row)) setQueen(row+1);
		}
	}
	
    // 현재 퀸의 위치가 유망한지 점검하는 함수.
    // - 이전 퀸과 같은 열, 대각선 위치에 있는지 확인.
	public static boolean isAvailable(int row) {
		for(int j = 1; j < row; j++) {
			if((cols[j] == cols[row]) || (row - j == Math.abs(cols[row] - cols[j]))) {
				return false;
			}
		}
		
		return true;
	}
}