[SWEA] 2806. N-Queen - 자바

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=8#;return%20false;

SW Expert Academy

 

문제 :

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다.

퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.

 

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.

N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까?

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

 

설명 :

n이 4라면 아래와 같이 4*4 크기의 2차원 배열에서 퀸을 4개 놓았을때 공격하지 못하는 경우의 수는 2개다. (1은 퀸이 있는 자리 )

	1
			1
1
		1

		1
1
			1
	1

 

이렇게 2가지 경우가 나오기 때문에 답은 2이다.

그렇다면 이 문제를 풀기위한 단계를 설명한다.

 

1. 단계

 2차원 배열은 사용하지 않는다.  ( n이 커지면 처리시간이 너무 길어짐) 1차원 배열로 해결한다.  arr의 인덱스를 2차원 배열의 행, arr의 값을 2차원 배열의 j번째에 퀸이 있다고 생각하는 것이다. 상세한 설명은 아래 블럭 참고.

arr [] = {0, 3, 1, 2} 는
2차원 배열로 했을때 다음과 같다 (1은 퀸이 있다는 뜻)
1 0 0 0
0 0 0 1
0 1 0 0
0 0 1 0
이렇게 가능한 이유는 한 row에 퀸이 하나만 존재해야 하기 때문

 

2. 단계

dfs로 l (level) 0부터 시작하여 조건에 통과하면 중복순열로 arr배열을 채워줌. 

조건이란 같은열,대각선에 퀸의 존재유무이다.

통과하면 dfs(l+1)로 다음 퀸을 놓도록 자리를 재귀적으로 처리.

결과적으로 퀸을 놓을때마다  l+1되기때문에  퀸을 n개만큼 놓으면 정답으로 출력할 answer변수 1증가

//퀸 놓을수 있는지 검사하는 함수
public boolean isValid(int i) {
    for (int j=0; j<i; j++) {
        //열에 퀸이 있는지 판별
        if (arr[i] == arr[j]) return false;
        //대각선에 일치하는게(퀸이) 있는지 판별
        if (Math.abs(i - j) == Math.abs(arr[i] - arr[j])) return false;
    }
    return true;
}

전체코드

import java.util.*;
public class Main {
    static int n,answer;
    static int[] arr;
    public boolean isValid(int i) {
        for (int j=0; j<i; j++) {
            //열에 퀸이 있는지 판별
            if (arr[i] == arr[j]) return false;
            //대각선에 일치하는게(퀸이) 있는지 판별
            if (Math.abs(i - j) == Math.abs(arr[i] - arr[j])) return false;
        }
        return true;
    }
    public void dfs(int l){
        if(l==n) {
            System.out.println(Arrays.toString(arr));
            answer++;
            return;
        }
        for(int i=0; i<n; i++) {
            arr[l] = i;
            // 해당 arr(행)과 i(열)에 퀸을 놓을 수 있는지 확인
            // if조건을 안걸고 dfs(l + 1) 를 하면 중복순열이 되면서 모든 경우의 수를 if(l==n)인순간 만듦
            if (isValid(l)) dfs(l + 1);
        }
    }
    public static void main(String[] args) {
        Main M = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        arr=new int[n];
        M.dfs(0);
        System.out.println(answer);
    }
}