백트래킹(backtracking)에 대하여 (N-Queen).Java

안녕하세요 오늘은 백트래킹에 대한 포스팅을 작성해보겠습니다.

 

목차

1. 백트래킹 기법

2. DFS와의 차이점

3. 대표적 문제예시

4. N-Queen 코드

 

한 줄 요약

백트래킹은 모든 후보 검사가 아니다, 즉 완전탐색이 아니다.

 

 

1. 백트래킹 기법

• 어떤 노드의 유망성을 점검한 후 에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다.
• 가지치기(pruning): 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다.

 

2. 백트래킹과  DFS와의 차이

• 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써, 시도 횟수를 줄인다.
• 깊이 우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단할 수 있다.
• N! 가지의 경우의 수를 가진 탐색의 경우, 경우의 수가 너무나 많아 이를 모두 탐색하는 것은 매우 비효율적이다.
• 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만, 최악의 경우에는 모든 경우를 탐색할 수도 있다.

 

 

3. 백트래킹을 활용한 대표 문제 (N-Queen)

- n X n 서양 장기판에서 배치한 Queen들이 서로 위협하지 않도록 n개의 Queen을 배치하는 문제

Think small, 작은 n에 대해 먼저 생각하기

• n = 4일 때,

모든 경우의 수 : 4 x 4 x 4 x 4 = 256

 

루트 노드에서 리프노드까지의 경로는 DFS를 활용하여 그 해답 후보 중에서 해답을 찾을 수 있다. 그러나 이 방법을 사용하면 해답이 될 가능성이 전혀 없는 노드의 후손 노드들도 모두 검색해야 하므로 비효율적이다.

 

백트래킹을 이용한 알고리즘은 다음과 같은 절차로 진행된다.

1. 상태 공간 트리의 깊이 우선 검색을 실시한다.

• 상태 공간 트리: 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리

2. 각 노드가 유망한 지 검사한다.

3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다.

 

 

그럼 Java코드로 풀이한 내용을 보시죠!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main { 
    static int cnt, N;
    static int[] dr = {-1,-1,-1}, dc = {-1,0,1}; //조사할 윗 방향 설정 왼쪽위,위,오른쪽위
    static int[][] chessMap;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            N = Integer.parseInt(br.readLine());
            cnt = 0;
            chessMap = new int[N][N];
            Put_Queen(0);
            System.out.println(cnt);
    }

    //각 열마다 체크
    public static void Put_Queen(int row) {
        //기저 조건
        if (row >= N) { 여기까지 왔다는 얘기는?! 놓을 수 있는 경우라는 얘기!
            cnt++;
            return;
        }
        //재귀 조건
        for (int j = 0; j < N; j++) {
            //현재 row의 j번째 열에 퀸을 위치시킬 수 있는 지 파악
            if (!QueenCanPosition(row, j)) continue; //거기 놓을 수 없어? 그럼 다음 열보자
            chessMap[row][j] = 1; //여기 한 번 둬볼까?
            Put_Queen(row + 1); // 뒀다고 치고, 다음 거 확인 해보자
            chessMap[row][j] = 0; //둔 거 다시 치워야지
        }
    }
    public static boolean QueenCanPosition(int i,int j) { //Queen을 놓아도 되는 지 여부 판단
        for(int dir = 0; dir<3; dir++) { //세 방향 탐색하자
            int r = i;
            int c = j;
            while(r >= 0 && c >= 0 && c < N){  //경계조건에 있을 땐
                r += dr[dir];
                c += dc[dir];
                if(r >= 0 && c >= 0 && c < N && chessMap[r][c] == 1) return false; //거긴 못 지나간다..
            }
        }
        return true; // 들어가도 된다는 얘기
    }
}

 

 

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

9663번: N-Queen

 

 

읽어주셔서

감사합니다