Backtracking

 

 

 

분할정복이나 dp처럼 문제를 풀기 위한 전반적인 전략 같은 알고리즘이다.

 

문제의 해가 될 수 있는 후보군들 중에서 특정 조건에 부합하는 해의 집합을 찾을 때 사용한다.

 

처음에 해가 될 수 있는 후보를 하나 선택하고, 처음 선택과 연관해서 다음 해가 될 수 있는 후보를 하나 선택하는 방식으로 진행하고, 만약 연관된 해를 구할 수 없다면 처음으로 돌아가서(backtrack) 다시 후보를 선택한다. 

 

 

 

 

트리 자료구조와 연관해서 이해하면 편하다.

각 후보를 DFS방식으로 확인하며, 조건에 맞지 않으면 해의 후보가 될 수 있는 위치로 돌아가 다시 탐색한다.

 

 

조건에 맞지 않아서 연관된 요소를 모두 포기하는 기법을 Pruning이라고 하고, 해당 요소가 조건에 부합하는지 확인하는 기법을 Promising이라고 한다.

 

 

 

백트래킹의 대표적인 예시 중 하나인 N - Queen문제에 대해 알아보자.

 

 

 

N * N 크기의 체스판에서 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제이다.

 

Pruning을 생각해보자. 퀸은 수평 방향으로 이동할 수 있기에 한 행에는 하나의 퀸만 존재할 수 있다.

맨 위에 존재하는 행부터 시작해 퀸을 배치하고 다음 행에 퀸을 배치할 수 있는 후보를 탐색하며 진행한다.

 

 

Promising을 생각해보자. 퀸은 수직 방향과 대각 방향으로도 이동할 수 있다. 

수직 방향은 열에 대해서 확인하면 되고, 대각선은 (탐색하는 퀸의 행 좌표 - 현재 퀸의 행 좌표) == (탐색하는 퀸의 열 좌표 - 현재 퀸의 열 좌표) 조건을 만족하는 경우이기에, 이 조건을 만족하는 경우는 대각선으로 처리하면 된다.

 

 

 

import java.util.ArrayList;

public class NQueen {
    
    public boolean isAvailable(ArrayList<Integer> candidate, Integer currentCol) {
        Integer currentRow = candidate.size();
        for (int index = 0; index < currentRow; index++) {
            if ((candidate.get(index) == currentCol) || (Math.abs(candidate.get(index) - currentCol) == currentRow - index) ) {
                return false;
            }
        }
        return true;
    }
    
    public void dfsFunc(Integer N, Integer currentRow, ArrayList<Integer> currentCandidate) {
        if (currentRow == N) {
            System.out.println(currentCandidate);
            return ; // 탐색을 마무리한 경우.
        }
        
        for (int index = 0; index < N; index++) { // 모든 열을 확인한다.
            if (this.isAvailable(currentCandidate, index) == true) {
                currentCandidate.add(index);
                this.dfsFunc(N, currentRow + 1, currentCandidate); // dfs는 재귀로 구현
                currentCandidate.remove(currentCandidate.size() - 1); // 조건에 부합하지 않으면 삭제한다.
            }
        }
    }   
}

 

 

재귀호출은 반복하고 또 반복해서 익숙해져야한다..