백트래킹(Backtracking)과 DFS(Depth-First Search)

1. 백트래킹? DFS?

백트래킹과 DFS는 어떻게 보면 분리하기가 애매한 개념이다. 굳이 분리해서 의미를 부여하자면 끝까지 가느냐 돌아오느냐로 간단하게 생각해볼 수 있다. DFS 역시 재귀를 통해서 구현하므로 시작 기점으로 돌아오는 개념이 들어가 있기는 하지만, 백트래킹의 경우 현재 가는 길이 더 이상의 해가 아니라고 판단되면 되돌아오는 것을 의미한다.

간단하게 DFS 개념을 정리하자면, 가능한 모든 경로를 깊이 우선으로 탐색하는 것을 의미한다. DFS에 대한 자세한 내용은 아래 게시글을 통해 알아보자!

DFS(Depth-First Search) + BFS 복습

2. 백트래킹(Backtracking)

자, 그러면 백트래킹(Backtracking)은 '해가 아니라면 다시 돌아온다'고 언급했는데, 이 부분을 가지치기라고 부른다. 즉 불필요한 경로는 굳이 끝까지 탐색하지 않겠다는 것이다. 직관적으로 봐도 백트래킹의 효율성은 얼마나 가지치기를 적절히 해내느냐의 문제로 볼 수도 있을 것이다.

백트래킹과 관련된 몇 가지 용어들은 아래와 같다.

• 유망함(promising): 진행중인 경로가 해답을 찾을 가능성이 있음
• 유망하지 않음(nopromising): 진행중인 경로가 해답을 찾을 가능성이 없음
• 가지치기(pruning): 유망하지 않은 하위 트리를 잘라냄

백트래킹(Backtracking)을 이용하여 풀이하는 문제들은 대표적으로 'N-Queen', '배낭문제', '순열/조합' 등의 유형들이 있다. 그 중 가장 대표적인 'N-Queens'에 대해 살펴보자.

9663번: N-Queen

'N-Queen' 문제는 N x N 크기의 체스판에서 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제다. 퀸은 룩과 비숍의 움직임을 가져갈 수 있는 체스 말로써 수직/수평/대각선으로 공격할 수 있는 말이다. 퀸이 움직일 수 있는 방법은 아래와 같다.

사진은 원피스의 퀸으로 체스와는 무방하다

퀸은 언급한 바와 같이 수직/수평/대각선으로 공격할 수 있으므로 우리는 직감적으로 각 행, 열에 하나의 퀸 만을 배치시켜야 한다는 것을 알 수 있다. 하지만 이것을 DFS로 탐색할 경우, N x N x N x N의 경우의 수가 발생한다. 각 행/열 마다 이를 배치할 수 있는지를 탐색해야 하기 때문이다. 이 말인 즉슨 N이 커질 경우 더이상 완전탐색을 수행할 수 없다는 것을 의미하고, 백트래킹의 가지치기가 필요한 순간이라는 것을 발견할 수 있다. 그럼 어떻게 가지치기를 할 것인가?

0행 0열에 퀸을 배치했다면, 1행에서는 (1행 0열), (1행 1열)에 퀸을 놓는 경우의 수는 더 이상 탐색할 필요가 없다는 것을 알 수 있다. 즉, 탐색을 진행하는 과정에서 이전 결과가 다음 진행에 영향을 미치고 있으므로, 해를 찾을 수 없는 가지는 끊어 냄으로써 탐색의 횟수를 줄일 수 있게 된다.

이 과정을 각 행마다 반복함으로써 탐색해야할 경로를 최소한으로 줄이는 것이 바로 백트래킹의 핵심이라고 볼 수 있다.

그럼 배치된 퀸의 위치와 어떤 경로가 더 이상 퀸을 놓을 수 없는 위치임을 판단하기 위해 어떤 자료 구조를 선택할 것인가? 이차원 평면이라는 점에서 이차원 배열을 가장 먼저 떠올릴 수 있지만, 단순 일차원 배열로도 풀 수 있다.

다음과 같이 성공적으로 퀸을 배치한 상황을 일차원 배열로 표현하면 아래와 같다.

• (1, 3, 0, 2)

그렇다. 배열의 idx를 행번호로 배열의 value를 열번호로 사용하면 충분히 일차원 배열로도 풀 수 있게 된다. 중요한 것은 퀸을 놓을 때 같은 열에 퀸이 존재하는지, 혹은 대각선 방향에 퀸이 존재하는지를 어떻게 판단할 것인가다. 같은 열의 경우 일차원 배열의 value가 동일한 것이 있는지를 확인하면 되고, 대각선의 경우 기울기 개념을 사용하면 된다.

• abs(target_idx - current_idx) == abs(arr[target_idx] - arr[current_idx])

이차원 배열에서 대각선 상에 존재한다는 것은 두 지점의 기울기가 1 혹은 -1 이라는 것을 의미하고 이는 X 변화량과 Y 변화량이 동일하다는 것을 의미한다.

---

여기까지의 개념을 이해했다면 코드를 직접 구현해보고, 어려움이 있다면 아래 코드를 참고하자.

public class Main {
    static int N;
    static int[] cols;
    static int result = 0;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        
        cols = new int[N];
        
        backTracking(0);
        
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
	
    static void backTracking(int cnt) {
        // N개의 퀸을 모두 배치했다면, 경우의 수 증가
        if(cnt == N) {
            result++;
            return;
        }
			
        for(int i = 0; i < N; i++) {
            cols[cnt] = i;
            
            // 퀸을 배치하는 것이 가능한 경로라면, 추가 탐색 진행
            if(isPossible(cnt))
                backTracking(cnt + 1);
        }
    }
	
    // 퀸을 배치할 수 있는지 확인
    static boolean isPossible(int cnt) {
        for(int i = 0; i < cnt; i++) {
            // 동일한 열 혹은 대각선에 위치한 퀸이 존재한다면 놓을 수 없다
            if(cols[i] == cols[cnt] || Math.abs(cnt - i) == Math.abs(cols[cnt] - cols[i]))
                return false;
        }
        return true;
    }
}

---

3. 참고 문제

1) [Silver 3] 15650번 N과 M(2)

N과 M시리즈의 문제들은 백트래킹을 연습하기 좋은 문제 유형들이니, 모두 풀어볼 것을 추천한다.

15650번: N과 M (2)

2) [Gold 5] 4672번 Don't Get Rooked

4672번: Don't Get Rooked

3) [Gold 3] 1941번 소문난 칠공주

1941번: 소문난 칠공주