98 삐약 : 백준 9663 | N-Queen [바킹독| 백트래킹 |JAVA]

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

 

package BKD_0x0C_BackTracking;

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

public class BOJ_9663 {

    static int N;
    static int count=0;

    static boolean[] visited1 = new boolean[40];
    static boolean[] visited2 = new boolean[40];
    static boolean[] visited3= new boolean[40];

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

        N = Integer.parseInt(br.readLine());

        func(0);
        System.out.println(count);

    }

    static void func(int cur){
        if(cur == N) {
            count++;
            return;
        }

        for( int i=0;i<N;i++){
            if(visited1[i] || visited2[cur+i] || visited3[cur-i+N-1]) {
                continue;
            }

            visited1[i] =true;
            visited2[cur+i] = true;
            visited3[cur-i+N-1] = true;
            func(cur+1);
            visited1[i] =false;
            visited2[cur+i] = false;
            visited3[cur-i+N-1] = false;

        }


    }
}

 

 

 

 

---

 

 

조건

각 행에 하나의 퀸 말이 있어야 한다.

 

퀸의 행동 범위

• 행 : 한 행에 한 말만 배치 할 것이기 때문에 신경 안씀
• 열 : y 좌표가 일치하는가
• 증가형태 대각선 : x+y가 같은 값인가
• 감소형태 대각선 : x-y가 같은 값인가

 

 

---

 

함수 정의

void func(cur) :  cur 번째 행에 말을 배치한다. 

 

Base Condition:

cur == N

 

 

Recursion

각 열과 대각선의 점유 상태를 나타내는 isUsed 변수를 사용

• isUsed1[y] : 열
• isUsed2[cur + y] : 증가 대각선
• isUsed3[cur-y+n-1] : 감소 대각선

 

(cur,i) 좌표에 퀸을 배치 가능 할 때

1. 점유 상태 변경
2. func(cur+1) 함수 호출