Algorithm 12일차

알고리즘에서 백트래킹을 활용할 수 있다.

모든 조합을 시도하다가 답이 될 가능성이 없는 조합은 사전에 가지치기하는 전략을 백트래킹이라고 한다.

백트래킹으로 N-Queens 문제를 풀 수 있다. N-Queens 문제의 정의는 아래와 같다.

1. N * N 체스판에 한 행에 한 개의 Queen을 놓는다.
2. 그렇게 총 N개의 Queen을 놨을 때,
   Queen이 서로를 공격하지 않는 경우의 수는 몇 개인가?

8-Queens 문제를 가정하여 문제를 풀어보자.

첫 번째로 생각할 수 있는 방안은 64개 칸에 8개의 퀸을 놓는 경우를 완전 탐색하는 것이다.
그러면 경우의 수는 64C8로, 40억을 넘어가므로 문제 풀이가 불가하다.
따라서 불가능한 경우는 애초에 가치지기 함으로써 탐색 가짓수를 많이 줄일 수 있다.

불가능한 경우는 아래와 같다.

1. 퀸과 퀸이 같은 행에 있는 경우
2. 퀸과 퀸이 같은 열에 있는 경우
3. 퀸과 퀸이 대각선 상에 있는 경우

해당 경우를 가지치기하여 문제를 풀면 아래와 같이 풀 수 있다.

import java.util.Scanner;

public class NQueen {
	static int N, answer;
	static int[] col;
	
	static void setQueen(int rowNo) {
		if (!isAvailable(rowNo - 1)) {
			return;
		}
		
		if (rowNo > N) {
			answer += 1;
			return;
		}
		
		for (int c = 1; c <= N; c++) {
			// temp = col[rowNo];
			col[rowNo] = c;
			setQueen(rowNo+1);
			// col[rowNo] = temp;
		}
	}
	
	static boolean isAvailable(int rowNo) {
		for (int k = 1; k < rowNo; k++) {
			if (col[k] == col[rowNo] || Math.abs(col[rowNo] - col[k]) == rowNo - k) {
				return false;
			}
		}
		
		return true;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		col = new int[N+1];
		
		setQueen(1);
		System.out.println(answer);
		
		sc.close();
	}
}

출력 결과는 아래와 같다.

92

※ 2차원 배열인 행, 열을 1차원 배열로 표현할 수 있다.
1차원 배열의 인덱스를 행, 값을 열로 생각하면 2차원 배열을 1차원 배열로 표현가능하다.
유용한 표현법이므로 잘 숙지해두자.