[백준] 9663_N-Queen / 백트래킹, DFS

 

 

Gold

 

 

문제

 

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

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

 

 

입력

 

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

 

 

출력

 

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

 

 

---

 

풀이

import java.util.*;

class Main {
    static int count;
    static int N;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        count = 0;

        boolean[] cols = new boolean[N];     // 열 탐색
        boolean[] diag1 = new boolean[N*2];  // 대각선 탐색1 (왼쪽 위, 오른쪽 아래)
        boolean[] diag2 = new boolean[N*2];  // 대각선 탐색2 (오른쪽 위, 왼쪽 아래)

        func(0, cols, diag1, diag2);
        
        System.out.println(count);
    }

    public static void func(int r, boolean[] cols, boolean[] diag1, boolean[] diag2){
		
        // 모든 행에 퀸을 배치했을 경우 카운트 증가
        if(r == N){
            count += 1;
            return;  
        }

       // 현재 행(r)의 열을 탐색
        for(int col=0; col<N; col++){
        	
            // 해당 열, 대각선에 이미 퀸이 배치되어있다면 스킵
            if(cols[col] || diag1[r-col+N] || diag2[r+col])  
                continue;

            cols[col] = true;
            diag1[r-col+N] = true;
            diag2[r+col] = true;

            func(r+1, cols, diag1, diag2);

            cols[col] = false;
            diag1[r-col+N] = false;
            diag2[r+col] = false;
            
        }
    }   
}

 

 

해결방법

 

1. 퀸을 놓을 수 있는지 확인하기 위해 3개의 배열을 사용.

• boolean[] cols: 퀸이 놓인 열을 탐색
• boolean[] diag1: 퀸이 놓인 대각선을 탐색 ( 왼쪽 위, 오른쪽 아래). 대각선의 수는 열이나 행보다 많다. N*2-1
• boolean[] diag2: 퀸이 놓인 대각선을 탐색 ( 오른쪽 위, 왼쪽 아래)

2. 첫번째 행부터 시작하여 퀸을 놓을 수 있는 자리 탐색.

• 열과 대각선을 탐색한 후 퀸을 놓을 수 없다면 스킵
• 퀸을 놓을 수 있다면 그 위치에 퀸을 배치한 후 열과 대각선 배열을 업데이트 후 다음행(r+1) 탐색
• 열  = col
• 왼쪽 대각선 = r-col+N ( (0,0) (1,1) (2,2) 모두 동일 대각선 / 음수가 발생할 수 있기 때문에 + N)
• 오른쪽 대각선 : r+col

3. 마지막 행까지 탐색하였을 경우 r이 N과 크기가 같다면 count + 1

 

 

 

 

 

---

https://www.acmicpc.net/submit/9663/82797339