이미지 출처는 모두 풀이 참고 링크입니다
백트래킹으로 풀 수 있는 대표적인 문제이다
✅ 백트래킹
백트래킹은 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는 것이다.
가능한 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴본다
문제 풀이에서는 주로 DFS등으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어 답이 될 수 없는 상황을 정의하고, 그러한 상황일 경우 탐색을 중지시키고 그 이전으로 돌아가 다른 경우를 탐색한다.
✅NQUEEN 문제
✅ 문제 해결방법
문제 해결 방법은 위와 같다.
2번에서 되돌아가는 과정이 백트래킹이다.
또한 체스판이어서 2차원 배열을 생각했지만, 2차원 배열을 사용할 필요가 없다.
1차원 배열의 인덱스가 행 정보를 담고 배열의 값이 열 정보를 담게 하면 된다.
✅ 소스 코드
import java.util.*;
public class Main{
public static int N=0;
public static int count=0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
// 열 정보만 담는 1차원 배열
int[] chess = new int[N];
nQueen(0,chess);
System.out.println(count);
}
// 백트래킹 하는 함수
public static void nQueen(int row, int[] chess){
if (row==N){
count+=1;
return;
}
for (int i=0; i<N; i++){
chess[row] = i;
if (promising(row,chess)){
nQueen(row+1,chess);
}
}
}
// 유망성 판단하는 함수
private static boolean promising(int row, int[] chess) {
for (int i=0; i<row; i++){
if (chess[row]==chess[i]||(row-i==Math.abs(chess[row]-chess[i]))){
return false;
}
}
return true;
}
}✔ 열 정보만 담는 1차원 배열을 활용한다
✔ nQueen 함수
row==N 일 경우, N개의 퀸을 전부 놓은 것으로 count+=1 하고 리턴한다
아닐 경우, i=0 ~ N-1 까지 N개의 열 중 0번째 부터 퀸을 놓아본다.
퀸을 놓은 후 promising 함수로 규칙에 위배되지 않는지 검사한다.
검사에 통과한다면, 다음 열에 대해 nQueen을 호출한다
✔ promising 함수
chess 배열의 전 행까지 순회하며 조건에 위배되는 상황이 있는지 검사한다.
새로 놓은 퀸이 기존 퀸과 같은 열에 있거나, 대각선상에 있으면 (대각선상에 있는지는 열 값의 차이 = 행 값의 차이 인지로 판단) false를 반환한다.
아닐 경우 true를 반환해 다음 행에 대해 NQueen이 호출되도록 한다.
✅ 스도쿠 문제
스도쿠 문제 역시 백트래킹으로 풀 수 있다.
나는 백트래킹 과정에서 잘못 생각해서 고생하다가 답을 봤다.
✅ 소스 코드
import java.util.Scanner;
public class Main {
public static int[][] arr = new int[9][9];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
arr[i][j] = in.nextInt();
}
}
sudoku(0, 0);
}
public static void sudoku(int row, int col) {
// 해당 행이 다 채워졌을 경우 다음 행의 첫 번째 열부터 시작
if (col == 9) {
sudoku(row + 1, 0);
return;
}
// 행과 열이 모두 채워졌을 경우 출력 후 종료
if (row == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
// 출력 뒤 시스템을 종료한다.
System.exit(0);
}
// 만약 해당 위치의 값이 0 이라면 1부터 9까지 중 가능한 수 탐색
if (arr[row][col] == 0) {
for (int i = 1; i <= 9; i++) {
// i 값이 중복되지 않는지 검사
if (possibility(row, col, i)) {
arr[row][col] = i;
sudoku(row, col + 1);
}
}
arr[row][col] = 0;
return;
}
sudoku(row, col + 1);
}
public static boolean possibility(int row, int col, int value) {
// 같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사
for (int i = 0; i < 9; i++) {
if (arr[row][i] == value) {
return false;
}
}
// 같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
for (int i = 0; i < 9; i++) {
if (arr[i][col] == value) {
return false;
}
}
// 3*3 칸에 중복되는 원소가 있는지 검사
int set_row = (row / 3) * 3; // value가 속한 3x3의 행의 첫 위치
int set_col = (col / 3) * 3; // value가 속한 3x3의 열의 첫 위치
for (int i = set_row; i < set_row + 3; i++) {
for (int j = set_col; j < set_col + 3; j++) {
if (arr[i][j] == value) {
return false;
}
}
}
return true; // 중복되는 것이 없을 경우 true 반환
}
}소스코드는 출처의 코드를 베껴왔다.
sudoku를 호출해서 스도쿠 판을 채워나가다가 잘못 채워서 더이상 못 채우는 경우가 있을 때 백트래킹을 돌아오는 과정이 핵심이다.
위와 같은 스도쿠 판에 대해 이런 식으로 채워나가게 된다
1~6 까지는 문제 없이 채워 나가는데, 7을 채우려고 하면 사각형 조건에 걸려서 채울 수 없다.
// 만약 해당 위치의 값이 0 이라면 1부터 9까지 중 가능한 수 탐색
if (arr[row][col] == 0) {
for (int i = 1; i <= 9; i++) {
// i 값이 중복되지 않는지 검사
if (possibility(row, col, i)) {
arr[row][col] = i;
sudoku(row, col + 1);
}
}
arr[row][col] = 0;
return;
}
sudoku(row, col + 1);즉 sudoku 함수의 위 부분에서 if 이하의 for문에서 i=1~9 까지 넣어도 possibility(row,col,i)가 false가 되어서 채우지 못하고 for문을 탈출하게 된다.
함수 스택은 위와 같은 상황이다. sudoku(0,6)은 return 했고,
sudoku(0,5)로 돌아와 빨간색 칸에 남은 for문 i=7부터 다시 진행한다.
하지만 i=7,8,9 모두 사각형 조건에 위배되게 된다. 따라서 sudoku(0,5) 또한 리턴하는데, 이 때 arr[row][col]=0으로 빨간색 칸을 0으로 만들어 놓고 return해야 백트래킹이 성공적으로 이루어진다. (칸을 다시 비웠으므로)
