백트래킹

백트래킹의 개념

 

해를 찾는 도중 해가 아니면, 되돌아가서 다시 해를 찾아가는 방법

=> 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 방법

=> 만족하지 않는 것이 확인되면 부모 노드로 돌아가 다음 자식 노드를 확인한다.

=> 가지치기라고 말하는데 불필요한 부분을 굳이 연산하지 않아 효율적이다.

=> 최악의 경우에는 여전히 지수함수 시간을 요할 수 있어 반드시 답을 얻는 것은 아님

 

깊이우선탐색(DFS) + 가지치기(Pruning)
DFS만으로는 답이 될  수 없는 경우도 모두 리프까지 탐색하므로 이 때 특정 조건문을 작성하여  조건에 해당하지 않으면 해당 경로를 가지는 않는 가지치기 방식을 적용해 백트래킹을 구현할 수 있다.

 

백준 9663

import java.util.Scanner;

public class Main {

	static int n, cnt;
	static int[] map;
	static boolean[] selected;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		map = new int[n + 1];
		selected = new boolean[n + 1];
		cnt = 0;
		// 2차원 배열 대신 1차원 배열로 구현하는데
		// 배열의 인덱스가 행 값, 각 인덱스의 값이 열 값

		queen(1); // 각 행의 위치에 값을 넣어 어떤 열에 위치할지 모든 경우 추출
		System.out.println(cnt);
		sc.close();
	}

	private static void queen(int i) {
		// 기저조건 -> 모든 행의 값을 뽑으면 종료
		//System.out.println("i: " + i);
		if (i == n + 1) {// 0부터 n-1까지 뽑기 때문
			// System.out.println(Arrays.toString(map));
			cnt++;
			return;
		}

		else {
			for (int j = 1; j <= n; j++) {
				if (selected[j]) { // 사용되었으면 이제는 못써 중복 안되거든
					continue;
				}
				map[i] = j;

				// 하나 뽑을 때마다 다른 퀸의 공격을 받을 가능성이 있는지 확인
				if (!safe(i)) {
					// System.out.println(safe(i));
					continue;
				}
				selected[j] = true; // 이 값 사용되었다는 뜻
				queen(i + 1);
				map[i] = 0; // 꼭 필요한가
				selected[j] = false; // 사용 원상복구
			}
		}
	}

	private static boolean safe(int i) {
		// System.out.println("safe 실행");
		for (int k = 1; k < i; k++) {
			for (int j = k + 1; j <= i; j++) {
				if (map[k] - k == map[j] - j) { // 우하향 공격받는다.
					return false;
				}
				if (map[k] + k == map[j] + j) { // 좌하향 공격받는다.
					return false;
				}
			}
		}
		return true; // 위의 조건에 걸리지 않는다면 안전하겠죠!
	}
}