250905

조금만 버텨서 빨리 뜨자 뒤도안돌아보고가야함

인간아닌사람들

상대를 말아야 함

• 백트래킹 백준
• 백트래킹 프로그래머스
• 시험장 나누기

isPossible메서드부터

package backTracking;

import java.util.Scanner;

public class backjoonNQueen {
	// 이렇게 하는 이유는 메서드 세개 모두에서 사용가능하게 하려고
	static int n;
	static int[] arr; // arr[i] = i번째 행에서 퀸이 놓인 열 위치
	static int answer = 0; // 해답 개수

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 체스판 크기, Queen의 개수
		

		// arr[i] = j는 i번째 행(row)의 퀸이 j번째 열(column)에	있다는 의미
		// arr 배열의 인덱스는 행, 값은 열
		int[] arr = new int[n];
		
		dfs(0); // 0번째 행부터 시작
		System.out.println(answer);		
	}
	
	static void dfs(int row) {
		// n은 체스판 크기이자 퀸 개수
		// 즉, 0 ~ n-1행까지 퀸을 다 놓았을 때
		// row == n 이면 row == 4이까 0~3행에 퀸을 다 놓은 상태
		// 이 시점에서 더 이상 행을 내려가서 퀸을 놓을 필요가 없음
		// 따라서 return; 으로 현재 DFS 호출 종료 → 이전 행으로 돌아감
		if (row == n) { // row == n → 모든 행에 퀸을 놓았다 → 해답 1개 완성 ★
			answer++;
			return; // 이전 행으로 돌아감 ★
		}
		
		for (int col = 0; col < n; col++) {
			arr[row] = col; // row행 col열에 퀸 노힉
			if (isPossible(row)) { // 지금까지 놓은 퀸들이 서로 공격하지 않으면
				dfs(row + 1); // 다음 행으로 이동
			}
		}
	}

	private static boolean isPossible(int row) {
		// TODO Auto-generated method stub
		return false;
	}

}