[알고리즘/JAVA] 백트래킹(Backtracking) : 개념 (N-Queen / 스도쿠)
백트래킹(Backtracking)
어떤 문제를 풀 때에 모든 경우의 수를 체크해보면서, 해가 아닌 케이스의 경우를 만나면, 그 이전 상태로 되돌아가서 다른 케이스를 체크하는 알고리즘이다.
상태 공간은 문제를 해결하기 위해 가능한 모든 상태의 집합을 의미하는데, 이를 트리 형태로 표현할 수 있을 때 유용하게 사용될 수 있는 방법이다. 즉 상태공간 트리를 탐색하는 알고리즘이라고 보아도 무방하다.
<상태공간 트리>
1. 깊이 우선 탐색(DFS) : 백트래킹은 DFS와 같이 재귀적으로 깊숙하게 확장해나가면서 해를 찾아간다. 그렇지만 DFS와 달리 해를 찾아가는 중 해당 경로가 틀린 해답이라는 것을 알아챈다면 바로 이전 상태로 Backtracking한다.
2. 유망성(Promising) 판단과 가지치기 : 현재 상태가 해를 찾을 수 있는 상태인지를 판단하고, 만약 그렇지 않다면 더 이상 해당 경로를 탐색하지 않고, 이전 상태로 되돌아가서 다음 경로를 탐색한다.
즉 깊이 우선 탐색에서, 모든 경로를 완전히 탐색하지 않고, 해당 경로를 온전히 탐색하기도 전에 유망하지 않다고 판단하면 다음 경로를 탐색하는 방식이다.
따라서 프로그래밍으로 문제를 해결할 때, 전체 상태공간 트리를 탐색하는 재귀호출 내에서 현재 마디가 유망한가에 대한 조건을 검사하고, 해당 조건을 통과하면 다음 마디의 탐색을 재귀호출 하도록 주로 설계하게 된다.
4-Queens 문제로 보는 백트래킹
4개의 Queen을 서로 상대방을 위협하지 않도록 4x4 체스판에 배치시키는 문제이다.
Queen이 다른 Queen을 공격할 수 있는 조건은 같은 행, 같은 열, 대각선에 Queen이 위치하는 것으로, 해당 위치들을 피해서 배치시키는 문제를 말한다.
상태공간 트리
따라서 퀸을 배치시키는 경우를 상태공간 트리로 나타내면 다음과 같이 나타낼 수 있다. Depth는 체스판의 1행부터 4행까지 퀸을 배치시킬 수 있는 경우의 수를 의미한다.
즉, (1,1) -> 1행 1열에 퀸을 위치시켰다면, 2행에서는 (2,1), (2,2), (2,3), (2,4) 중 하나에 위치시킬 수 있고, 3행에서는 해당 경우의 수들에 대해서 또 경우의 수가 갈릴 것이다.
딱 보면 알겠지만, 위의 상태공간 트리 전체를 탐색하기에는 비효율적이므로, 유망성을 판단하고 정답이 될 수 없다면 탐색을 하지 않도록 하는 것이 백트래킹의 핵심이다.
예를 들어서 (1,1)에 퀸을 위치시켰다면 다음 Depth에서 같은 열(2,1), 대각선(2,2)에는 퀸을 위치시킬 수 없을 것이다. 따라서 해당 가지에 대해서는 탐색을 하지 않는 것이 가지치기이다.
백트래킹을 적용시켰을 때의 상태공간 트리의 모습이다.
유망성 판단 및, 가지치기를 적용하여 탐색할 상태공간 트리의 크기가 훨씬 줄어든 것을 알 수 있다.
해당 4-queens 문제를 두 가지 경우로 풀이한다면 검색하는 마디의 개수가 이렇게나 차이가 난다.
DFS : 155마디, Backtracking : 27마디
언제 사용해야 할까?
백트래킹은 문제의 조건에 따라서 많이 좌우되지만 보통 지수의 시간 복잡도를 가진다.
최악의 경우는 모든 상태공간 트리를 탐색해야 되는 경우가 될 것이다. 따라서 분명히 모든 경우의 수를 체크해야 하는 경우를 최적화하여 풀이 시간을 단축시킬 수는 있지만, 브루트 포스와 같이 모든 경우의 수를 따지는 알고리즘이므로 최악의 경우가 발생할 것을 알고 있어야 한다.
그렇지만 다이나믹 프로그래밍(DP), 그리디 등을 사용해서 풀이할 수 없고, 모든 경우의 수를 따져봐야 하는 경우가 분명히 존재한다. 브루트 포스가 여전히 사용되는 이유이기도 하다.
완전 탐색이 필요한 경우, 순열 또는 조합과 관련된 경우, 0또는 1로 결정되는 의사 결정의 집합을 구하는 문제 등에서 백트래킹 을 사용할 수 있는 확률이 높다는 것을 알아두자.
문제 : N-Queen (백준 9663)
위에서 설명한 4-queens 문제를 N개의 퀸에 대한 문제로 변경한 대표적인 백트래킹 알고리즘의 문제이다.
재귀 호출과 백트래킹
public class Main {
static int[][] array;
static int n;
static int count = 0;
static void nQueen(int depth){ //현재 행(Depth)의 상태공간 트리 탐색
// 모든 행에 대해 Queen의 배치를 마쳤을 경우
if(depth == n){
count++;
}
//현재 행에서 퀸을 놓을 수 있는 경우의 수
for(int i = 0; i < n; i++){
if(isPromising(depth, i)){ //퀸을 놓을 위치가 유망한지(Promising) 판단
array[depth][i] = 1; // 해당 위치에 퀸을 배치한 상태로 변경
nQueen(depth + 1); //다음 Depth의 상태공간 트리 탐색
array[depth][i] = 0; // 탐색 종료 후 퀸을 없애서 원래 상태로 변경
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
array = new int[n][n];
for(int[] row : array){
Arrays.fill(row, 0);
}
nQueen(0);
System.out.println(count);
}
}
기본적인 알고리즘의 설계이다.
1. 입력과 변수 설정 : N을 입력받아서, 체스판으로 사용할 N*N 크기의 배열을 만든다. 해당 배열에서 0은 퀸을 놓지 않을 경우, 1은 퀸을 놓을 경우로 사용될 것이다.
2. 상태공간 트리 : 가능한 모든 퀸의 배치 상태를 나타낸다. 각 트리의 깊이는 퀸이 배치된 행, 각 노드의 가지는 해당 행에 퀸을 놓는 열의 위치를 나타낼 것이다.
3. 백트래킹 알고리즘
상태공간 트리 탐색 : 전체적으로는 현재 행(Depth)에 대해 퀸을 배치했다면 재귀 호출을 통해 다음 행에 대한 탐색을 진행하는 방식이다. 메인 함수에서 nQueen(0)을 호출하여 맨 처음 행부터 탐색을 시작하고, 재귀적으로 N번째 행까지의 탐색이 진행될 것이다.
탐색 완료 조건 : 만약 현재까지 배치한 퀸의 수가 N과 같다면(Depth는 0부터 시작하므로), 해가 나온 것이므로 조건을 설정한다.
탐색 : 현재 행에 대해 Queen을 배치 가능한 열에 대해서 모든 경우의 수에 대해서 다음을 진행한다.
- 유망성 판단 : 해당 행의 해당 열에 Queen을 배치해도 이전 행에 배치한 Queen들과 충돌되지 않는지 판단한다 (isPromising())
- 재귀 호출 : 해당 마디가 유망하다면 퀸을 배치하여 상태를 변경한 이후 다음 행(Depth)에 대해 탐색하는 재귀 호출을 수행한다.
- 원래 상태로 복원 : 재귀 호출이 끝나면 해당 마디에서 갈 수 있는 경우의 수 까지 모두 가본 것이다. 따라서 퀸을 원래 배치 상태로 돌려놓고 현재 Depth의 다른 경우의 수에 대한 탐색을 진행한다.
유망성 판단
static boolean isPromising(int row, int col){
//같은 열 확인
for(int i = 0; i < row; i++){
if(array[i][col] == 1){
return false;
}
}
// 왼쪽 위 대각선 확인
int i = row;
int j = col;
while(i >= 0 && j >= 0){
if(array[i][j] == 1){
return false;
}
i--;
j--;
}
// 오른쪽 위 대각선 확인
i = row;
j = col;
while(i >= 0 && j < n){
if(array[i][j] == 1){
return false;
}
i--;
j++;
}
return true;
}
해당 행의 해당 열에 퀸을 배치가 가능한 지에 대한 유망성을 판단하는 메서드이다.
위의 코드에서 같은 행에는 1개의 Queen만이 배치되도록 작성하였으므로 같은 열, 왼쪽 위 대각선, 오른쪽 위 대각선에 퀸이 존재하는 지에 대해서만 체크하면 된다.
아래쪽은 재귀호출에 의해 Depth가 깊어지면서 탐색될 것이고, 아직 탐색하지 않았으므로 탐색하지 않는다.
전체 코드
public class Main {
static int[][] array;
static int n;
static int count = 0;
static boolean isPromising(int row, int col){
//같은 열 확인
for(int i = 0; i < row; i++){
if(array[i][col] == 1){
return false;
}
}
// 왼쪽 위 대각선 확인
int i = row;
int j = col;
while(i >= 0 && j >= 0){
if(array[i][j] == 1){
return false;
}
i--;
j--;
}
// 오른쪽 위 대각선 확인
i = row;
j = col;
while(i >= 0 && j < n){
if(array[i][j] == 1){
return false;
}
i--;
j++;
}
return true;
}
static void nQueen(int depth){ //현재 행(Depth)의 상태공간 트리 탐색
if(depth == n){
count++;
}
//현재 행에서 퀸을 놓을 수 있는 경우의 수
for(int i = 0; i < n; i++){
if(isPromising(depth, i)){ //퀸을 놓을 위치가 유망한지(Promising) 판단
array[depth][i] = 1; // 해당 위치에 퀸을 배치한 상태로 변경
nQueen(depth + 1); //다음 Depth의 상태공간 트리 탐색
array[depth][i] = 0; // 탐색 종료 후 퀸을 없애서 원래 상태로 변경
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
array = new int[n][n];
for(int[] row : array){
Arrays.fill(row, 0);
}
nQueen(0);
System.out.println(count);
}
}
문제 : 스도쿠 (백준 2580)
스도쿠 문제도 대표적인 백트래킹 문제 중 하나이다. N-Queen과 유사한 형태의 풀이를 사용해서 백트래킹 알고리즘에 대한 복기를 해보자.
문제는 9 * 9 크기의 스도쿠 판이 주어지면, 0으로 되어있는 칸들을 숫자로 스도쿠 조건에 알맞게 채워넣는 것이다.
스도쿠의 조건은 같은 행, 같은 열, 속한 3*3 영역에서 1~9까지의 수가 하나씩 있어야 한다는 것이 조건이다.
앞의 N-Queen과는 다르게 여러개의 해답 중 한 가지만 찾아내면 되고, 첫번째 해를 찾았을 때 탐색을 계속해서 진행하게 되면 시간초과가 걸릴 수 있다는 점이다. 따라서 탐색을 종료시키는 로직에 대해서 추가해주어야 한다.
public class Main {
static int[][] board = new int[9][9];
static boolean solve(int row, int col){
// 열이 9일 경우 -> 다음 행에 대한 탐색 진행
if(col == 9){
return solve(row + 1, 0);
}
// 행이 9일 경우 -> 해답 도출, 탐색 종료
if(row == 9){
print();
return true;
}
// 해당 행/열에 수를 채워넣어야 하는 경우
if(board[row][col] == 0){
for(int k = 1; k <= 9; k++){ //1부터 9까지 수를 채워넣어 보아서 가지뻗기
if(isPromising(row, col, k)){ //유망성 판단
board[row][col] = k; // 수를 채워넣어 상태 변경
boolean isSolve = solve(row, col + 1); // 수를 채운 후 재귀호출을 통해 다음 행/열 탐색
if(isSolve){ //해가 나왔다면 탐색 종료
return true;
}
board[row][col] = 0; // 재귀호출 종료 후 다시 0으로 설정하여 상태 복구
}
}
return false; // 해당 칸에 모든 수를 채워넣는 경우에 대해서 실패했을 경우
}
// 해당 행/열에 이미 수가 있는 경우
else{
return solve(row, col + 1); // 다음 마디로 이동
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for(int i = 0; i < 9; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < 9; j++){
board[i][j] = Integer.parseInt(st.nextToken());
}
}
solve(0, 0);
}
}
1. 입력과 변수 설정 : 스도쿠 판에 대해서 9*9 배열을 사용한다.
2. 상태공간 트리 : 모든 행/열에 대해서 탐색하고, 0인 요소에 대해서 1~9까지를 채워넣을 수 있는 경우의 수에 대해서 탐색한다.
3. 백트래킹 알고리즘
상태공간 트리 탐색 : 현재 행/열에 대해 퀸을 배치했다면 재귀 호출을 통해 다음 열에 대한 탐색을 진행한다. 메인 함수에서 solve(0,0)을 호출하여 맨 처음 1행 1열부터 탐색을 시작하고, 재귀적으로 9행 9열까지의 탐색이 진행될 것이다.
탐색 완료 조건 : 만약 현재 행 인덱스가 9일 경우 해가 나온 것이므로 결과값으로 참을 반환하고 스도쿠판을 출력하여 종료한다.
행 이동 조건 : 만약 현재 열 인덱스가 9일 경우, 현재 행에 대해서는 탐색을 완료한 것이므로, 다음 행의 1열(인덱스 0)에 대해서 탐색한다.
탐색, 현재 요소가 0일 경우 : 수를 넣어야 하므로, 현재 행/열에 대해 1~9까지의 수를 넣을 수 있는 경우의 수에 대해서 진행한다.
- 유망성 판단 : 해당 행/열에 해당 수를 넣어도 스도쿠 조건을 만족하는지 판단한다 (isPromising())
- 재귀 호출 : 해당 마디가 유망하다면 수를 채워넣어 상태를 변경한 이후 다음 열(혹은 다음 행)에 대해 탐색하는 재귀 호출을 수행한다. 만약 해가 나왔다면 문제 조건이 여러개의 해 중 첫번째 스도쿠판을 출력하라고 했으므로 종료한다.
- 원래 상태로 복원 : 재귀 호출이 끝나면 해당 마디에서 갈 수 있는 경우의 수 까지 모두 가본 것이다. 따라서 수를 채워넣기 이전 상태인 0으로 되돌린다.
탐색, 현재 요소가 0이 아닌 경우 : 수를 채워넣어야 할 필요가 없으므로 다음 열(혹은 다음 행)에 대한 탐색을 진행한다.
static boolean isPromising(int row, int col, int k){
//같은 행에 같은 수가 있는 지 판단
for(int i = 0; i < 9; i++){
if(board[row][i] == k){
return false;
}
}
//같은 열에 같은 수가 있는 지 판단
for(int i = 0; i < 9; i++){
if(board[i][col] == k){
return false;
}
}
//3*3 내부에 같은 수가 있는 지 판단
int startRow = (row / 3) * 3; //0~9를 [0,2][3,5][7,9]로 매칭
int endRow = ((row / 3) * 3) + 2;
int startCol = (col / 3) * 3;
int endCol = (col / 3) * 3 + 2;
for(int i = startRow; i <= endRow; i++){
for(int j = startCol; j <= endCol; j++){
if(board[i][j] == k){
return false;
}
}
}
return true;
}
해당 행/열에 해당 수를 넣어도 되는 지에 대한 유망성을 판단하는 함수이다.
같은 행, 같은 열, 3*3 범위 안에 같은 수가 있다면 유망하지 않은 것이다. 따라서 해당 조건들을 검사해주도록 하자.
전체 코드
public class Main {
static int[][] board = new int[9][9];
static boolean isPromising(int row, int col, int k){
//같은 행에 같은 수가 있는 지 판단
for(int i = 0; i < 9; i++){
if(board[row][i] == k){
return false;
}
}
//같은 열에 같은 수가 있는 지 판단
for(int i = 0; i < 9; i++){
if(board[i][col] == k){
return false;
}
}
//3*3 내부에 같은 수가 있는 지 판단
int startRow = (row / 3) * 3; //0~9를 [0,2][3,5][7,9]로 매칭
int endRow = ((row / 3) * 3) + 2;
int startCol = (col / 3) * 3;
int endCol = (col / 3) * 3 + 2;
for(int i = startRow; i <= endRow; i++){
for(int j = startCol; j <= endCol; j++){
if(board[i][j] == k){
return false;
}
}
}
return true;
}
static boolean solve(int row, int col){
// 열이 9일 경우 -> 다음 행에 대한 탐색 진행
if(col == 9){
return solve(row + 1, 0);
}
// 행이 9일 경우 -> 해답 도출, 탐색 종료
if(row == 9){
print();
return true;
}
// 해당 행/열에 수를 채워넣어야 하는 경우
if(board[row][col] == 0){
for(int k = 1; k <= 9; k++){ //1부터 9까지 수를 채워넣어 보아서 가지뻗기
if(isPromising(row, col, k)){ //유망성 판단
board[row][col] = k; // 수를 채워넣어 상태 변경
boolean isSolve = solve(row, col + 1); // 수를 채운 후 재귀호출을 통해 다음 행/열 탐색
if(isSolve){ //해가 나왔다면 탐색 종료
return true;
}
board[row][col] = 0; // 재귀호출 종료 후 다시 0으로 설정하여 상태 복구
}
}
return false; // 해당 칸에 모든 수를 채워넣는 경우에 대해서 실패했을 경우
}
// 해당 행/열에 이미 수가 있는 경우
else{
return solve(row, col + 1); // 다음 마디로 이동
}
}
static void print(){
StringBuilder sb = new StringBuilder();
for(int k = 0; k < 9; k++){
for(int i = 0; i < 9; i++){
sb.append(board[k][i]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for(int i = 0; i < 9; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < 9; j++){
board[i][j] = Integer.parseInt(st.nextToken());
}
}
solve(0, 0);
}
}
References
Algorithms in C++, Robert Sedgewick 저
Addison Wesley Fundamentals of Algorithmics, Gilles Brassard 저
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘/JAVA] 누적 합 (Prefix Sum) (0) | 2024.04.20 |
|---|---|
| [알고리즘/JAVA] 동적 계획법(DP) : 개념 (파도반 수열 / 1로 만들기 / 계단 오르기) (0) | 2024.04.16 |
| [알고리즘/JAVA] 정렬 알고리즘 : 선택, 삽입, 버블, 병합, 퀵 정렬 (0) | 2024.04.05 |
| [자료구조/JAVA] 해시 테이블 (Hash Table) (0) | 2024.03.31 |
| [자료구조/JAVA] 허프만 코딩 (Huffman Coding) (0) | 2024.03.31 |
