[JAVA] 백준 9663 N-Queen_백트래킹

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

접근 : 

 

 - N 의 크기를 받는다.

 

 - 세로의 길이가 N 이므로 N개의 Queen을 놓기위해선 각 줄마다 1개의 Queen 이 존재해야 한다.

 

 - Queen을 놓을 때, + 모양으로 겹치는 Queen이 있는지 확인한다.

 

 - Queen을 놓을 때, x 모양으로 겹치는 Queen이 있는지 확인한다.

 

 - Queen을 n 개 까지 놓으면 카운트를 1 증가 시킨다.

 

 - depth = Queen의 갯수 = y 좌표로 동일하게 사용하여 불필요한 메모리를 줄인다.

 

 * 메모리 제한으로 인하여 Queen 객체를 구현하여 OOP 로 구현할 수 없다.

 

 

 - 코드 구현 

 

import java.io.*;

public class Main {

	// 놓을 수 있는 경우의 수 탐색
	static class Dfs {
		private int n;
		private int result;
		private int[] selected_x;

		public Dfs(int n) {
			this.n = n;
			this.selected_x = new int[n];
			this.result = 0;
		}

		public void doDfs(int depth) {

			// 놓인 말의 갯수가 n 개일 때 카운트 증가 후 종료
			if (depth == this.n) {
				result++;
				return;
			}

			// x 좌표 첨부터 끝까지 진행
			for (int i = 0; i < this.n; i++) {
			
				// 현재 위치가 말을 놓을 수 있으면 위치 정보 저장 및 다음 말 위치 탐색
				if (isAvalivable(i, depth)) {
					this.selected_x[depth] = i;
					doDfs(depth + 1);
				}
			}
			return;
		}

		boolean isAvalivable(int x, int depth) {
			int exsist_x;
			// 퀸이 첫번째로 놓이는 경우
			if (depth == 0) {
				return true;
			}

			for (int j = 0; j < depth; j++) {
				exsist_x = this.selected_x[j];
				// | 모양에 queen 이 있는지 검사 ( ㅡ 방향은 y가 항상 아래로 1씩 증가함으로 고려 x)
				if (x == exsist_x) {
					return false;

				// X 모양에 queen 이 있는지 검사
				} else if (Math.abs(x - exsist_x) == Math.abs(depth - j)) {
					return false;
				}
			}
			return true;
		}

		public int getResult() {
			return result;
		}

	}

	public static void main(String[] srgs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		Dfs dfs = new Dfs(n);
		dfs.doDfs(0);
		System.out.println(dfs.getResult());
	}
}

 

 

 - 간소화

import java.io.*;

public class Main {
    private static int n;

    private static int[] selected;
    private static int ans;

    static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        selected = new int[n];
        ans = 0;
        br.close();
    }

    static boolean isAvaliable(int x){
        for(int i = 0 ; i < x ; i++){
            if(selected[x] == selected[i]) return false;
            if(Math.abs(selected[x] - selected[i]) == Math.abs(x - i)) return false;
        }
        return true;
    }

    static void calFunc(int now){
        if(now == n) {
            ans++;
            return;
        }

        for(int i = 0 ; i < n ; i++){
            selected[now] = i;
            if(isAvaliable(now)) calFunc(now+1);
        }
    }

    public static void main(String[] args) throws IOException{
        input();
        calFunc(0);
        System.out.println(ans);
    }
}