백준_9663_N-Queen

문제

9663번: N-Queen

풀이

파이썬으로 작성한 코드는 시간초과로 테스트를 통과하지 못했다. N의 범위가 작다보니 정답 값을 리스트에 저장해서 통과하는 방법이 가능하다. 그 이외의 다른 방법을 찾지 못해 자바로 코드를 작성하였다.

 

queen의 위치가 다음과 같을 때 [2, 4, 1, 3]처럼 저장할 수 있다.

1	1	queen	1
queen	2	2	2
3	3	3	queen
4	queen	4	4

후보자 n(1~N)은 arr의 각각의 원소에 대해 조건을 만족해야 한다.

1) 같은 행에 위치하지 않는다.

• arr = [2, 4, 1] 이라고 할때 같은 후보자n이 2, 4, 1이 아닌지 확인해야 한다.

• n==arr[j]

2) 대각선 상에 위치하지 않는다.

• d(index)==d(queen)인지 확인해야 한다.
• Math.abs(lv-j)==Math.abs(arr[j]-n)

코드

package project;

import java.util.*;

public class Main {
    public static int N = 0;	// 체스판의 크기
    public static int ans = 0; 	// 정답의 개수
    
    public static void solve(int[] arr, int lv){
        if (lv==N) { 	// N개의 원소가 채워졌다면
            ans++;		// 정답의 개수+1
            return;
        }
        
        for (int n=1; n<=N; n++){
            boolean check = true;	// n이 모든 원소에 대해 조건을 만족하는지를 저장
            for (int j=0;j<lv;j++){
                if (n==arr[j] | Math.abs(lv-j)==Math.abs(arr[j]-n)){
                    check = false;	// n이 조건을 만족하지 못함
                    break;
                }
            }
            if (check==true){	// 모든 조건을 만족한다면, 
                arr[lv] = n;	// 해당 위치에 원소를 대입하고
                solve(arr, lv+1);	// 재귀호출
            }
        }
        
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        int[] arr = new int[20];
        solve(arr, 0);
        System.out.println(ans);
    }
}

알고리즘

• 브루트포스 알고리즘
• 백트래킹