Backtracking(백트래킹)

Backtracking(백트래킹)

1. 백트래킹이란?

백트래킹은 모든 조합의 수(완전 탐색)를 조건이 만족할 때(유망할 때) 만 살펴보는 것이다.

Backtracking은 임의의 집합(set)에서 주어진 기준(criterion) 대로 원소의 순서(sequence)를 선택 하는 문제를 푸는 데 사용한다.

2. DFS VS Backtracking

(1) DFS

DFS는 가능한 모든 경로를 탐색한다.

불필요한 것 같은 (유망하지 않은) 경로도 탐색하기 때문에 경우의 수를 줄이지 못한다.

(2) Backtracking (DFS + 조건)

DFS를 통해 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다.

백트레킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.

DFS 등으로 모든 경우의 수를 탐색하는 과정에서 조건문을 이용해서 유망한 지 판단한다.

3. Backtracking의 유망성(Promising) 판단

(1) 유망하다(promising)

해가 될 가능성이 있다면 유망하다

(2) 유망하지 않다(nonpromising)

해가 될 가능성이 없다면 유망하지 않다

(3) 가지치기(pruning)

유망하지 않는 노드에 가지 않는 것을 가지치기라고 한다.

상태 공간 트리를 DFS(깊이 우선 탐색)을 하는 중 해가 될만한지 검사한 후 유망하지 않다고 결정되면 그 노드의 부모로 돌아가(Backtraking) 후 다음 부모 노드의 자식 노드를 탐색합니다.

4. N-Queen 문제

Backtraking의 가장 기본적인 문제이다.

문제 : 서양 장기판에 어떤 두 여왕말도 같은 행, 열 대각선에 있지 않도록 n개 여왕말을 놓을 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

(1) 퀸이 이동할 수 있는 위치

상하좌우 및 대각선으로 거리 제한 없이 한 방향으로 이동이 가능하다.

(2) 유망 조건

(1) 같은 행에 있으면 안 된다

일차원 배열을 이용해서 각 행에 여왕말 1개만 올 수 있도록 한다.

(2) 같은 열에 있으면 안 된다.

promising() method를 이용해서 같은 열에 있는지 검사한다.

(3) 대각선에 위치하면 안 된다.

promising() method를 이용해서 대각선에 위치하였는지 검사한다.

* 대각선 검사

ex) 3,1위치에 여왕말이 있고 6,4위치에 여왕말이 있다고 생각해보자.

|3-6| == |1-4|

두 위치의 행의 차이의 절댓값과 열의 차이의 절댓값이 같다면 두 말은 대각선에 위치해 있다.

(3) 소스코드

import java.util.Scanner; public class BF_9663 { static int[] chess; static int N; static int count; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); N = scanner.nextInt(); chess = new int[N]; backtracking(0); System.out.println(count); } static void backtracking(int depth) { if(depth == N) { count++; return; } else { for (int i = 0; i

공유하기 글 요소 저작자표시

from http://choiyeonho903.tistory.com/46 by ccl(A) rewrite - 2021-10-14 02:00:31