BOJ - 9663 N-Queen

leehyunjon·2022년 7월 12일

boj 백트래킹 브루트포스

9663 N-Queen : https://www.acmicpc.net/problem/9663

Problem

Solve

문제 접근은 어렵지 않았다. 시간초과와의 싸움이 길었을 뿐이다..

1차 풀이

N*N의 2차원 배열에 퀸을 놓는 브루트 포스 알고리즘과 백트래킹을 사용해서 N개의 퀸을 놓았을 때 모든 배열을 돌면서 퀸을 놓은 자리를 찾아 가로,세로,대각선 방향을 모두 확인했다.

이렇게 하면 퀸을 놓는데 O(N^N), 배열을 찾는데 O(N^2*N)으로 지금 생각해보면 정말 터무니 없는 풀이 방법이다.

2차 풀이

다른 풀이에서 힌트만 얻어 풀어보았다.

퀸은 같은 행에서 다른 퀸을 놓을 수 없기 때문에 매개변수로 퀸을 놓는 행을 받아서 재귀할때마다 행+1로 넘겨주었고 열만 비교하여 해당 (행,열)에 퀸을 놓을 수 있는지 체크하는 함수를 돌려 가능할 때 퀸을 설치하는 백트래킹을 사용했다.

static void setQueen(int count, int N, int y) {
		if (count == N) {
			answer++;
			return;
		}

		for (int j = 0; j < N; j++) {
			if (board[y][j] == 0 && validation(y,j,N)) {
			board[y][j] = 1;
			setQueen(count + 1, N, y + 1);
			board[y][j] = 0;
			}
		}

	}
    
static boolean validation(int y, int x, int N){
		for(int d=0;d<8;d++){
		int ny = y+dy[d];
		int nx = x+dx[d];
		while(ny>=0&&nx>=0&&ny<N&&nx<N){
			if(board[ny][nx]==1) return false;
		
			ny+=dy[d];
			nx+=dx[d];
		 }
		}
		return true;
	}

통과는 했지만 말도안되는 시간이 나와서 고민하다가 다른 풀이를 참고했다.

3차 풀이

2차 풀이에서 행값을 매개변수로 받았는데, 해당 행에 설치된 퀸의 열값을 1차원 배열에 저장해주는 방식을 사용하고 저장된 열값 정보를 가지고 세로,가로에 퀸이 있는지 확인하고 대각선에 있는 좌표는 (x,y)의 대각선에 있는 (A,B)좌표라 예를 들면 (A-x) == (B-x)가 성립된다.(어떻게 이런생각을 하는지 대단한거같다..)

매개변수로 받은 행에서 퀸을 놓을 수있는지 확인한 후 가능하다면 열값을 저장하는 1차원 배열에 해당 열을 저장한 후 반복하는 방식이다.

static void setQueen(int count, int N, int y) {
		if (count == N) {
			answer++;
			return;
		}

		//해당 행에서 퀸을 놓을 수 있는 열 조회
		for (int j = 0; j < N; j++) {
			if(validation(y,j)){
				col[y] = j;	//해당 행에서 놓을 수 있는 열 저장.
				setQueen(count+1, N, y+1);
			}
		}
	}
    
static boolean validation(int y, int x){
		//퀸을 놓고 싶은 행의 이전에 놓았던 행의 열 조회
		for(int r=0;r<y;r++){
        	//이전에 놓았던 행의 열과 놓고싶은 위치의 열과 동일(세로에서 겹침)
			if(col[r]==x) return false;
            //대각선에서 겹침
			if((y-r)==Math.abs(x-col[r])) return false;
		}
		return true;
	}

Code

public class N_Queen {
	static int[] col;
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		col = new int[N];
		answer = 0;
		setQueen(0, N, 0);

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static void setQueen(int count, int N, int y) {
		if (count == N) {
			answer++;
			return;
		}

		for (int j = 0; j < N; j++) {
			if(validation(y,j,N)){
				col[y] = j;
				setQueen(count+1, N, y+1);
			}
		}

	}

	static boolean validation(int y, int x, int N){
		for(int r=0;r<y;r++){
			if(col[r]==x) return false;
			if((y-r)==Math.abs(x-col[r])) return false;
		}
		return true;
	}
}