9663 N-Queen (Java)

9663 N-Queen

문제 🌐

N-Queen 문제는 크기가 N×N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력

8

예제 출력

92

접근 방법

사실 난 체스… 가 퀸이 마음대로 움직일 수 있는 건지, 킹이 마음대로 움직일 수 있는 건지도 잘 몰랐음 ㅋㅋㅋ

백트래킹 알고리즘을 활용해서 구현해 보라는 스터디원들의 말에 차근차근 생각해 봤다.

먼저, 퀸은 체스판을 직선, 대각선으로 움직일 수 있는데 서로를 공격하지 못하는 상태가 되려면 다음의 경우가 존재해서는 안 된다.

1. 행 번호가 같음
2. 열 번호가 같음
3. 대각선 위치에 있음 (좌표값 중 x좌표의 차, y좌표의 차의 절댓값이 ±1)

4*4 체스판을 생각해 보면,

 

모두가 공격할 수 없는 상태고, 열 번호, 행 번호 모두가 다른 값을 가진다는 것을 알 수 있다.

그래서, 체스판이 2차원 공간이라고 해서 2차원 배열을 만들어 관리하지 않아도 된다는 것을 생각했다. !!행 번호, 열 번호가 겹칠 수 없기 때문에!! 스도쿠랑 비슷한 원리인 듯하다.

일차원 배열 points를 선언하여 index를 행 번호, index에 해당하는 값을 y 좌표로 관리할 수 있다.

백 트래킹 메소드를 만들었다. 시작하는 행 번호 r을 기준으로 (r, c) 좌표를 가지고 이전의 한 행씩 확인하고, 조건에 맞으면 한 행 더 앞으로 나아가는 방식이다. 이때 points에 (r, c) 좌표에 퀸이 자리잡고 있는 위치를 저장해 둔다.

처음엔 main 메소드에서 for문을 활용해 0,1 0,2 0,3 0,4 라고 시작점을 지정하고 시작했는데 for 문이 두 번 돌아서 원하는 값의 N배가 나왔다. 알고 보니 bt 안에서 도는 반복문으로 열에 대한 값을 이미 확인해 주고 있었던 것임~

	static void bt(int r, int N, int[] points) {
		// bt (r+1, N,  ...);
		if(r == N) {
			cnt++;
			return;
		}
		for (int dc = 0; dc<N; dc++) {
			boolean check = true;
			for (int i=0; i<r; i++) { 
				if (points[i]== dc || ((r-i) == Math.abs(points[i]-dc))) {
					check=false;
				}
			}
			if (check) {
				points[r] = dc;
				bt(r+1, N, points);
			}
		}	
	}

암튼 처음 자바로만! 알고리즘 문제를 풀어 보았다는 이야기…. 이 전에는 파이썬으로 먼저 구현하고 자바로 옮기는 방식으로 풀었는데, 이렇게 하다간 둘 다 멍청이가 될 것 같아 앞으로는 자바로 풀어보려 한다… 파이썬 안뇽.

Full Solution

import java.util.Scanner;
public class Main {
	static int cnt = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] points = new int[N];
		bt(0, N, points);
		System.out.println(cnt);
	}
	
	// backtracking: (시작줄, 체스판 한 변의 길이, 퀸의 좌표 저장)
	static void bt(int r, int N, int[] points) {
		// bt (r+1, N,  ...);
		if(r == N) {
			cnt++;
			return;
		}
		for (int dc = 0; dc<N; dc++) {
			boolean check = true;
			for (int i=0; i<r; i++) { 
				if ( points[i]== dc || ((r-i) == Math.abs(points[i]-dc))) {
					check=false;
				}
			}
			if (check) {
				points[r] = dc;
				bt(r+1, N, points);
			}
		}	
	}
}