백트래킹이란?
백트래킹은 알고리즘 기법 중 하나로, 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다.
여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 한다.
예시 문제 (N-Queen)
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
답안 코드
/*
* 프로그래머스 12952번. N-Queen
* https://school.programmers.co.kr/learn/courses/30/lessons/12952
*/
class Solution {
public int solution(int n) {
int[] board = new int[n]; // board[i] = j: i행 위치한 퀸의 위치
return dfs(board, 0, n);
}
/**
* 퀸을 놓는 경우의 수를 구하는 함수
*
* @param board 퀸의 위치를 저장한 배열
* @param row 현재 행
* @param n 체스판의 크기
* @return 퀸을 놓는 경우의 수
*/
private int dfs(int[] board, int row, int n) {
if (row == n) return 1;
int answer = 0;
for (int i = 0; i < n; i++) {
board[row] = i;
if (isPossible(board, row)) {
answer += dfs(board, row + 1, n);
}
}
return answer;
}
/**
* 퀸을 놓을 수 있는지 확인하는 함수
*
* @param board 퀸의 위치를 저장한 배열
* @param row 현재 행
* @return 퀸을 놓을 수 있는지 여부
*/
private boolean isPossible(int[] board, int row) {
for (int i = 0; i < row; i++) {
if (board[i] == board[row] || Math.abs(board[i] - board[row]) == row - i) { // 같은 열에 위치하거나 대각선에 위치하는 경우
return false;
}
}
return true;
}
}참고 - 가지치기
위 N-Queen 문제의 풀이에서 가지치기가 이루어지는 부분은 다음과 같다.
if (isPossible(board, row)) {
answer += dfs(board, row + 1, n); // 가지치기
}// 가지치기 함수
private boolean isPossible(int[] board, int row) {
for (int i = 0; i < row; i++) {
if (board[i] == board[row] || Math.abs(board[i] - board[row]) == row - i) { // 같은 열에 위치하거나 대각선에 위치하는 경우
return false;
}
}
return true;
}