백트래킹(Backtracking)의 개념과 DFS로의 확장, N-Queen

백트래킹

해를 찾는 중에 현재 선택한 루트(노드)가 해와 관련이 없다는 것을

알아차리면 중단하고(가지치기) 이전 단계로 돌아가 다른 루트를 탐색한다

해가 될 수 있는 노드(유망한 노드)만을 이용해 부분 탐색을 수행한다

​​

 

DFS

깊이 우선 탐색(Depth-First-Search), 맨 위 노드(루트)에서

하나의 가지(branch, 분기)를 완전히 탐색하고 다음 가지(분기) 넘어가는 방법

전체 탐색을 전제로 한다

​

DFS의 사용

자기 자신을 호출(재귀 호출)하는 순환 알고리즘 형태이다

무한 루프에 빠지지 않기 위해 방문했다는 기록을 남겨준다

​

예시

위의 트리를 탐색하는 메소드를 논리로 만들어보자(전위순회)

1. 현재 위치를 탐색하고 왼쪽 아래 노드로 이동합니다 2. 만약 왼쪽 아래 노드가 없거나 방문했다면 오른쪽 아래 노드로 이동합니다 3. 오른쪽 아래 노드도 없다면 상위 노드로 올라갑니다

이 메소드에 따라 1부터 탐색이 시작된다

( 파란색은 방문을 기록한 시점 )

1 → 2 → 3 → 4

4에 도달하면 오른쪽 노드가 없으므로 3규칙에 의해 올라간다

4 → 3 → 2 → 1

1에 도달하면 왼쪽 노드를 방문했으므로 오른쪽 노드인 5를 탐색한다

1 → 5 → 6 → 7

7에 도달하면 다시 올라오고 5에서는 오른쪽 노드가 있어 탐색한다

7 → 6 → 5 → 8

1로 올라가 맨 오른쪽 노드를 탐색한다

8 → 5 → 1 → 9 → 10

​

일일히 탐색할 필요없이

위 메소드를 계속 재귀호출해

전체 탐색을 마칠 수 있었다

​

​​

백트래킹과 DFS

백트래킹은 해를 찾아가는 기법 중 하나로 넓은 의미를 가진다

하지만 DFS는 트리, 그래프 등 특정 상황에서의 탐색을 위한 알고리즘 기법이다

둘은 같은 개념은 아니지만 탐색의 방향성에서 유사점을 가진다

백트래킹이 가지치기를 할 때 왔던 길을 되돌아간다는 점에서 재귀호출의 방식이

매우 유용하게 작용하는데 DFS의 방식을 혼용해 탐색 효율을 높힐 수 있다

​

​

N-Queen 백트래킹

N-Queen 문제는 백트래킹 대표 문제 중 하나로

DFS를 혼용한 예시가 될 수 있다

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

어떤 식으로 배치해야할까?

자세한 것은 모르지만 퀸은 한줄에 하나씩만 놓을 수 있다는

기본 논리가 필요하다

 

< N=4 , 4x4 체스판 위에 퀸 배치 >

일단 퀸을 첫번째 줄 첫번째 칸(1,1)에 배치한다

그러면 다음 줄에서는 1번과 2번 위치에 퀸을 올리지 못한다

다시 말해 2째줄에 1번과 2번은 유망한 노드가 아니게 되고

더 이상 탐색하지 않는다

​

그럼 남은 3번과 4번이 유망한 노드가 된다

2번째줄 3번째칸에 먼저 배치하면 다음과 같다

3번째줄에 놓으려고 살펴보니 유망한 노드가 없다

그럼 다시 3번은 가지치기하고 2번째줄 4번칸에 배치한다

 

3번째 줄에서는 2번에 밖에 둘 수 없고

4번째 줄에 퀸을 둘 수 없게 된다

이렇게 1번째줄 1번칸의 경우를 모두 살펴보았지만 해가 없었다

위와 같은 방식으로 1번째줄 2번칸인 경우, 3번칸인 경우, 4번 칸인 경우를

모두 살펴보는 것이다

4x4 체스판에서는 하나의 해가 나온다

​

N-Queen DFS

어떻게 위의 백트래킹을 코드로 만들 수 있을까?

DFS의 재귀호출 방식을 통해 구현할 수 있다

1번째 줄에 먼저 퀸을 놓아야 2번째 줄 어느 곳에 퀸을 놓을 수 있을지 결정할 수 있다 2번째 줄에 퀸을 놓아야 3번째 줄 어느 곳에 퀸을 놓을 수 있을지 결정할 수 있다 4번째 줄에 퀸을 놓을 수 있다면 그 값은 해가 된다

줄은 재귀의 깊이(Depth)가 된다

4에 도달하고 퀸을 놓았다면 값을 기록한다

이해를 위해 코드를 개략적으로 살펴본다

실제 코드는 더 아래에 있다

​

1. 먼저 위치를 체스판을 나타내보자

static boolean[][] chess = new boolean[4][4]; //4x4 체스판
static int count = 0; //해의 개수를 세어주기 위한 변수

 

2. 재귀호출 메소드를 만든다

//퀸 놓을 수 있는 가지 수를 세어주는 메소드
static void nQueen( 4, int Depth ){
    if( Depth == 4 ){
         count++
    }

    for(int i=0; i<4; i++){
         if( queenJudge(i, Depth) ){  //퀸을 놓을 수 있는지 메소드를 통해 확인한다
               chess[Depth][i] = true; //둘 수 있다면 방문 기록을 해준다
               nQueen( 4, Depth + 1 ); //방문 체크를 한 상태에서 다음 줄에 퀸을 둔다
               chess[Depth][i] = false; //빠져나올 때 방문 기록을 지워준다
         } 
    }
}

//현재 줄(Depth) i번째 칸에 퀸을 배치할 수 있는지 판단해주는 메소드
static boolean queenJudge( int i, int Depth ){
     if(Depth==0) return true; //1번째 줄에 두는 것은 제한 조건이 없다

     boolean judge = true; //아무 조건에도 걸리지 않으면 true가 결과값이 된다

     if( 대각선에 이미 다른 퀸이 있거나 같은 행, 열에 다른 퀸이 있다면 ){
         judge = false;
     }

     return judge;
}

 

3. 메인 클래스에서 메소드를 호출하고 누적된 count를 출력한다

public static void main(String[] args) {
        nQueen(4,0); //Depth가 0인채 시작
        System.out.print(count);
}

 

전체 코드

2차원 배열을 1차원 배열로 단순하게 만들 수 있다

import java.util.Scanner;
public class Main {
	static int count=0; //개수를 세어줄 변수 count
	static int[] selected; //현재까지 놓은 퀸의 위치를 선택하고 기록한 배열
    
    //지금까지 체스판에 올려놓은 퀸의 위치와 겹치는지 아닌지 확인하는 메소드
	static boolean check(int N, int Depth, int col) { //Depth가 곧 행, col은 열
		
        if(Depth==0)return true; //첫번째 줄에서는 제한 없이 퀸을 선택할 수 있다
        
		boolean judge=true;
        
		for(int i=0; i<Depth;i++) {
			if(Math.abs(i-Depth)==Math.abs(selected[i]-col) || selected[i]==col) {
             //대각선이거나 같은 줄이면 현재 위치에 퀸을 놓을 수 없다
				judge=false;
				i+=Depth;
			}
		}
		return judge;
	}
	
	
	static void nQueen(int N, int Depth) {
		if(Depth==N) { //재귀 깊이 N에 도달하면 모든 퀸을 놓았다는 뜻이므로 1개 추가한다
			count++;
			return;
		}
		for(int i=0; i<N;i++) {
			if(check(N,Depth,i)) { //메소드를 통해 퀸을 놓을 수 있으면 다음줄로 넘어간다(재귀호출)
				selected[Depth]=i; //값을 기록해주고
				nQueen(N,Depth+1); //다음 줄로 넘어간다
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		selected = new int[N];
		nQueen(N,0); //Depth는 0부터 시작한다
		System.out.print(count);
 }}

연산을 위해 사용한 메모리는 약 18000KB로 높은 효율을 보여준다는 것을 알 수 있다

이는 아래처럼 정답을 배열에 미리 적어놓고 호출하는 경우와 비슷한 효율이다

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		int[] a={0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596};
		System.out.print(a[s.nextInt()]);}}

 

​​

백트래킹 문제 예시​

백준 15649