[알고리즘] 백 트래킹 문제

백준 9663

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

public class Main {

	static int[] arr;
	static int N;
	static int de = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		N = Integer.parseInt(str);
		
		arr = new int[N];
		
		dfs(0);
		System.out.println(de);
}
	public static void dfs(int depth) {
		// dfs 재귀 함수로 계속 호출되면서 depth가 올라갈 때 depth==N면 정답인 경우의 수
		if(depth == N) {
			de++;
			return;
		}
		
        // 반복문 돌리면서, dfs 재귀 호출(possible에 부합할 시)
		for(int i = 0 ; i < N; i++) {
			arr[depth] = i;
			if(possible(depth)) {
				dfs(depth+1);
			}
		}	
	}
	
    // 이전의 퀸들과 대각선, 같은 행에 없음을 check
	public static boolean possible(int col) {
		
		for(int i = 0 ; i < col ; i++) {

		if(arr[i]==arr[col]) {
			return false;
		}

		else if(Math.abs(col-i) == Math.abs(arr[col]-arr[i])) {
			return false;
		}
			
		}
		
		return true;
	}
}

얻어갈 점:

• dfs vs 백 트래킹 => dfs: 완전 탐색을 기본으로 그래프를 모두 순회하기 때문에 불필요한 경로를 사전에 차단 불가 / 백 트래킹: 경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로라면 되돌아옴
• 백 트래킹으로 풀어야겠다 catch point => N x N "그래프"에 퀸을 "모두" 놓는 경우의 수를 탐색하는 것 + 퀸을 놓지 못하겠다 싶으면 탐색 중지
• 2차원 배열을 사용하지 않고 , 1차원 배열을 사용할 수 있는 이유? => 1개의 열에 퀸을 놓으면 해당 열에는 더 이상 놓을 수 없음 => arr[4]={0,1,2,3}이라면 1번째 열, 1번째 행에 퀸 / 2번째 열, 2번째 행에 퀸 ---- / 즉, 인덱스를 열로 삼고 값을 행으로 만들면 됨
• 대각선 조건 => 행 - 행 = 열 - 열 check