백준 9663번 자바 문제 답/해설(N-Queen문제)

[1] 백준 카테고리
단계별로 풀어보기
백트래킹
5단계 N-Queen

[2] 문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

1. 입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)

2. 출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

3. 예제 입력 1
8

4. 예제 출력 1
92

 

[3] 정답

1. 해설 미포함

import java.util.Scanner;
 
public class Main {
	public static int a;
	public static int count;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		for(int i = 1; i <= a; i++) {
			int[] col = new int[a+1];
			col[1] = i;
			dfs(col, 1);
		}
        
		System.out.println(count);
	}
	public static void dfs(int[] col, int row) {
		if(row == a) {
			count++;
		}else {
			for(int i = 1; i <= a; i++) {
			col[row+1] = i;
				if(funcTion(col, row+1)) {
				dfs(col, row+1);
				}
			}
		}
	}

	public static boolean funcTion(int[] col, int row) {
        
		for(int i=1; i < row; i++) {
			if(col[i] == col[row]) return false;
						
			if(Math.abs(i - row) == Math.abs(col[i] - col[row])) return false;
		}
		return true;
		}
}

 

2. 해설 포함

import java.util.Scanner;
// java.util.Scanner 클래스를 import 한다.
 
public class Main {
// 접근제어자 public으로 Main 클래스를 import한다.
	public static int a;
	// 접근제어자 public으로 메모리에 상주하게 int형 변수 a를 선언한다.
	public static int count;
	// 접근제어자 public으로 메모리에 상주하게 int형 변수 count를 선언한다.

	public static void main(String[] args) {
		// 접근제어자 public으로 메모리에 상주하게 리턴값이 없이 main 함수를 선언한다.
		Scanner sc = new Scanner(System.in);
		// Scanner 객체 sc 선언
		a = sc.nextInt();
		// 값을 입력받아 변수 a에 저장
		for(int i = 1; i <= a; i++) {
		// for문을 선언하고 i가 1~a일 때 괄호안의 문장을 반복한다.
			int[] col = new int[a+1];
			// 배열의 길이를 a+1로 int형 배열 선언 
						
			col[1] = i;
			// 변수 col[1]에 값 i 저장
						
			dfs(col, 1);
			// 매개변수 col, 1로 함수 dfs 선언
		}
        
		System.out.println(count);
		// count를 출력
	}
	public static void dfs(int[] col, int row) {
	// 접근제어자 public으로 메모리에 상주하게 리턴값이 없이 함수 dfs 선언
		if(row == a) {
		// if문을 선언한다. row==a일때 괄호안의 코드가 실행된다.
			count++;
			// count+1한 값을 변수 count에 저장한다.
		}else {
			// else문을 선언한다.
			for(int i = 1; i <= a; i++) {
			// for문을 선언한다. i가 1~N일때 괄호안의 문장이 반복된다.
			col[row+1] = i;
				// col[row+1]에 값 i를 저장한다.
				if(funcTion(col, row+1)) {
				// if문을 선언한다.
				dfs(col, row+1);
				// 매개변수 col, row+1으로 함수 dfs를 호출한다.
				}
			}
		}
	}

	public static boolean funcTion(int[] col, int row) {
		/* 접근제어자 public으로 메모리에 상주하게 리턴값이 boolean 매개변수 col, row로 
		함수 fucTion을 선언한다. */
        
		for(int i=1; i < row; i++) {
		// for문을 선언한다. i값이 1~<row일때 괄호안의 문장이 반복된다.
			if(col[i] == col[row]) return false;
			// if문을 선언한다. col[i] == col[row]일때 false가 리턴된다.

			if(Math.abs(i - row) == Math.abs(col[i] - col[row])) return false;
			/* if문을 선언한다. Math.abs(i - row) == Math.abs(col[i] - col[row])
			일때 false가 리턴된다. */
		}
		return true;
		// true가 리턴된다.
		}
}