[알고리즘] 백트래킹(Backtracking)

1. 백트래킹이란? 

백트래킹은 답을 찾다가 이 길이 아니다 싶으면 다시 돌아와서 다른 길을 탐색하는 알고리즘입니다.

백트래킹은 모든 경우의 수를 살펴보는 데에 기본을 두는데, 가능성이 없는 경우의 수는 배제하고 살펴보는 것이 특징입니다. 

 

2. N Queen 문제

 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

백트래킹 문제 중 가장 유명하다는 N-Queen 문제를 예시로 풀어보겠습니다.

문제는 위에 링크를 걸어놓은 백준 사이트를 참고해주시면 될 것 같습니다.

아래 한 블로그에서 사진을 퍼왔는데요, N-Queen을 백트래킹 알고리즘을 이용해서 탐색하는 방법을 적절히 나타내고 있는 그림입니다.

위 사진은 3*3 체스판을 예시로 들고 있는데요, 

행(row)별로 나누어 깊이를 더하며 탐색을 하고 있습니다. 

 

저는 만재송 님의 블로그를 참고하여 아래와 같이 풀어보았습니다.

import java.io.*;

import static java.sql.Types.NULL;

public class Main {

    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int col[]; //index에 행의 index, 값에 열의 index를 넣을 예정
    static int result=0;

    public static void main(String[] args) throws IOException {
        // write your code here
        N=Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            col=new int[N];
            col[0]=i;

            backtracking(1);
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }

    public static void backtracking(int row){
        if(row==N){
            result++;
            return;
        }

        for(int i=0;i<N;i++){
            col[row]=i;
            if(isAble(row)){
                backtracking(row+1);
            }
//            else{
//                col[row]=-1;
//            }
        }
    }

    public static boolean isAble(int row){
        for(int i=0;i<row;i++){
            //같은 열 검사
            if(col[i]==col[row]){
                return false;
            }
            //대각선 검사
            if(Math.abs(col[i]-col[row])==Math.abs(i-row)){
                return false;
            }
        }
        return true;
    }

}

 

col이라는 배열을 이용하여 배열의 index에는 행의 index, 배열의 값에는 열의 index 값을 넣어서 과거에 방문했던 퀸의 자리를 체크하였습니다.

위에서 언급했듯이 행별로 탐색을 진행했고, 매 행에서 isAble이라는 함수를 통해 유효성 검사를 실시해 유효한 경우에 다음 행으로 이동해 탐색을 할 수 있도록 코드를 작성했습니다.

 

 

출처:

https://www.programiz.com/dsa/backtracking-algorithm

Backtracking Algorithm

 

https://www.programmersought.com/article/78674658709/

Backtracking method and JAVA realization of N queen problem - Programmer Sought

https://thd0011.tistory.com/19

[알고리즘] 백트래킹 (Backtracking) 알고리즘