(23.08.20) (Baekjoon) 9663. N-Queen

 

9663번: N-Queen

 

- 시간 제한 : 10초

- 메모리 제한 : 128MB

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

8

예제 출력 1

92

 

체스의 퀸

체스의 '퀸'을 각 열마다 1개씩 둬서 모든 열에 퀸을 하나씩 놓을 수 있는 경우의 수를 구하는 문제다.

 

4개 열에 퀸을 하나씩 놓을 수 있는 경우

우선, 해법 자체는 간단하다.

'퀸이 없는 가장 윗열에서 퀸을 놓을 수 있는 곳에 퀸을 놓고 다음 열을 방문한다. 퀸을 놓을 수 없으면 이전 열의 퀸 위치를 변경한다. 모든 열에 퀸이 들어갈 수 있을 때까지 해당 과정을 반복한다.'

 

1~4열까지 있다고 가정하고, 1열 1행 > 2열 4행> 3열 2행 >4열 놓을 곳 없으므로 위치변경...

이러한 과정을 반복시키는 알고리즘을 구축하면 된다. 즉, 백트래킹이다.

 

우선, 순서가 적용되는 경우의 수를 찾는다... "순열(Permutation)"을 생각할 수 있다.

static void perm(int tgtIdx) { // tgtIdx번째 수를 찾는다
	if(tgtIdx == N) { // N번째 수까지 다 찾았으면
    	return; // 해당 순열을 꺼낼 수 있음.
    }
    
    for(int i = 0; i < N; i++) {
    	if(visit[i]) continue; // 이미 선택된 수면 생략
        
        visit[i] = true; // 해당 수는 선택됐음
        perm(i+1); // 다음 수 찾으러 이동
        
        // 다음 순열의 경우를 찾게 해주기 위해 visit[i]를 false로 되돌리기
        visit[i] = false;
    }
}

순열을 찾는 알고리즘이고, 해당 알고리즘을 응용하는 것이 이 문제를 푸는 키라고 할 수 있다.

 

위 알고리즘에선 '이미 선택된 수'를 생략 조건으로 내걸었지만, 해당 문제에선 '퀸이 방문할 수 없는 경우'를 생략 조건으로 내걸면 된다.

 

즉, 2번째 열부터 현재 놓을 퀸 위치의 현재 열, 완쪽 대각선 , 오른쪽 대각선에 퀸이 있으면 생략 조건이 된다!

 

1) 바로 위 생략조건

boolean[] visit1 = new boolean[N];

N개 열을 기준으로 탐색을 진행하기에 N개 값을 가지는 배열만 있으면 된다.

2) 왼쪽 대각선(우상좌하) 및 오른쪽 대각선(좌상우하) 생략조건

boolean[] visit2 = new boolean[2*N-1];

1) 의 생략조건은 같은 행을 보기 때문에 상관없지만, 대각선 생략조건은 행에도 영향을 미치기 때문에 퀸을 놓는 과정에서 기본 체스판 사이즈를 벗어날 수 있기 때문에 N의 2배 -1의 크기로 지정한다.

 

 

해당 생략조건을 기반으로 하여 순열을 사용하여 알고리즘을 전개하면 해결된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N;
	static int[] ar;
	static int ans = 0;
	static boolean[] visit1;
	static boolean[] visit2;
	static boolean[] visit3;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		ar = new int[N];
		visit1 = new boolean[N];
		visit2 = new boolean[2*N-1]; // 좌상 > 우하 대각선 확인
		visit3 = new boolean[2*N-1]; // 우상 > 좌하 대각선 확인

		
		queen(0);
		
		System.out.println(ans);
	}

	static void queen(int tgtIdx) {
		if(tgtIdx == N) {
			ans++;
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if(visit1[i] || visit2[tgtIdx+i] || visit3[tgtIdx-i+(N-1)]) continue;
			
			visit1[i] = true;
			visit2[tgtIdx+i] = true;
			visit3[tgtIdx-i+(N-1)] = true;
			queen(tgtIdx+1);
			
			visit1[i] = false;
			visit2[tgtIdx+i] = false;
			visit3[tgtIdx-i+(N-1)] = false;
		}
	}
}