[백준] 9663번 N-Queen JAVA (자바) 풀이

문제 9663번 (백트래킹)

 

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

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

 

 

 [입력]

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

 

 

 [출력]

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

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 

 

 pos메서드를 통해 참이 아니라면 다시 바꿔서 탐색한다 참이면 더 깊이 들어간다

 

 종료 조건) depth==N

 모두 종료되는 것이 아니라 N의 퀸을 세웠으면 경우의 수 1개를 카운트한다

 

 1. 퀸의 공격 방향은 대각선, 세로, 가로

• 같은 행, 같은 열, 같은 대각선은 피해야한다
• 하나의 행씩 구분할 것이기 때문에 행은 겹칠리가 없다
• arr는 1차원 배열로 인덱스는 행 / 값은 열이다

 

 2. depth는 행, i는 열

• pos메서드 내에서 조건에 통과된다면 arr[depth]에 i열 저장하기
• 다음행으로 넘어가서 nQueen메서드 실행한다
  
  

 3. pos 메서드

• 현재의 깊이까지 즉 현재의 행까지 쭉 훑어보면서 입력받은 열인 col과 같은 곳이 있는지 확인
  • 배열 안에 값이 저장되어 있다는 건 그열에 퀸을 놓았단 이야기 
  • 그 값이 동일하다면 해당부분에는 겹쳐서 놓을 수 없다 false
• 대각선의 거리 = 가로 차이와 세로 차이가 동일하다는 것
  • 같은 대각선에 있다하더라도 겹치기 때문에 false

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int count =0;
    static int arr[],N;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        nQueen(0);
        System.out.println(count);
    }
    static void nQueen(int depth){
        if(depth==N){
            count++;
            return;
        }
        for(int i=0;i<N;i++){
            arr[depth] = i;
            if(pos(depth)){
                nQueen(depth+1);
            }
        }
    }
    static boolean pos(int col){
        for(int i=0;i<col;i++){
            if(arr[col]==arr[i]){
                return false;
            }
            else if (Math.abs(col-i) == Math.abs(arr[col]-arr[i])) {
				return false;
			}
        }
        return true;
    }
}

 

 [해설]
     

 :  static int count =0;
    static int arr[],N;
   

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());  입력1
    arr = new int[N];  행을 인덱스로 둔 1차원 배열 (값은 모두 초기화)
        
 :  nQueen(0);  메서드 실행
    System.out.println(count);  최종 경우의 수 출력
 

  :  static void nQueen(int depth){  
        if(depth==N){  종료조건: N만큼의 퀸을 모두 채우면 
            count++;  경우의 수 카운트
            return;
        }
        for(int i=0;i<N;i++){  arr배열에 열 저장하기
            if(pos(depth,i)){  pos메서드를 통과한다면
                arr[depth] = i;  depth행에 i열 저장
                nQueen(depth+1);  다음 행 검사(재귀)
            }
        }
    }

 

 :  static boolean pos(int depth, int col){  행, 열
        for(int d=0;d<depth;d++){  이전행 모두 검사 (열 같은지, 대각선에 있는지)
            if (arr[d] == col || Math.abs(arr[d] - col) == Math.abs(d - depth)) {  
                return false; 조건에 부합하면 중복된 퀸이므로 false
            }
        }
        return true;  나머지는 true
    }


  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

 

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

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *