백 트랙킹

DFS와 백트래킹

DFS

• 깊이 우선 탐색으로 가능한 모든 경로를 탐색한다.
• 모든 경우의 수를 탐색하기 때문에 경우의 수를 줄이지는 못한다.

백트래킹

• 재귀적으로 문제를 해결 하지만 확인 중인 상태가 제한 조건에 맞는 지 확인하고 해당 상태가 조건에 맞지 않으면 제외한다.
• 위와 같이 조건에 맞지 않는 것을 제외 하는 것을 가지치기라고 한다.

N-Queen

백트래킹의 예시로 N-Queen 문제가 있다. 처음에 DFS으로 접근을 하였었으나 시간 초과가 발생하였다. 따라서 이를 해결하기 위해 조건에 맞지 않는 것을 제외 하는 방법으로 접근 하였다.

접근 방법

• 일차원 배열의 row 값은 퀸이 놓여져 있는 열의 값을 의미한다.
• 직선의 경우 배열의 값을 비교하면 되고 대각선은 기울기를 비교하면 된다.

dfs 재귀 Method

depth 즉 현재 주어진 배열의 길이만큼 재귀가 돌아가며 dp 배열에는 Queen이 놓아지는 위치가 출력이 된다.

public void dfs(int depth, int n) {  
    // 들어간 깊이가 주어진 n과 같아지만 멈춘다.  
    if (depth == n) {  
        answer += 1;  
        System.out.println(Arrays.toString(this.dp));  
        return;  
    }  
  
    for (int i = 0; i < n; i++) {  
        this.dp[depth] = i;  
        if (checkValid(depth)) {  
            dfs(depth + 1, n);  
        }  
    }  
}

loc ⇒ 행 dp[loc] ⇒ 열

dp 출력 예시

n이 4일 때

[1, 3, 0, 2]
[2, 0, 3, 1]

Queen을 둘 수 있는 지 검증

public boolean checkValid(int loc) {  
    boolean isContinue = true;  
    for (int i = 0; i < loc; i++) {  
		// 같은 세로 라인에 있는지 점검한다.
		// i < loc => 현재 라인 이전 까지 확인을 하는 것이다.
        if (this.dp[loc] == this.dp[i]) {  
            isContinue = false;  
        }  
        // 같은 기울기에 있는 지 점검한다. 
        // 대각선의 경우 행의 차이와 열의 차이가 같기 때문이다.
        if (Math.abs(loc - i) == Math.abs(this.dp[loc] - this.dp[i])) {  
            isContinue = false;  
        }  
    }  
    return isContinue;  
}