Programmers > 연습문제 > #32 N-Queen

N-Queen

 

문제: https://programmers.co.kr/learn/courses/30/lessons/12952?language=java

 

 

 

1. 문제 설명

 

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

 

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

제한사항

퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.

 

n은 12이하의 자연수 입니다.

 

 

 

2. 나의 코드

 

- 알고리즘을 공부했다면 누구나 다 아는 교과서 같은 문제.

- BackTracking 을 안다면 풀 수있는 문제이다.

- 아주 자세히 잘 설명 되어있는 블로그 => http://bumbums.tistory.com/3?category=728916

 

import java.lang.Math;

class Solution {
    int N;
    int [] cols;
    int ANSWER;
  public int solution(int n) {
      int answer = 0;
      this.N = n;
      cols = new int[n];
      backTracking(0);
      return answer = ANSWER;
  }
  public void backTracking(int level){
      if(level == N){
          ANSWER++;
      }
      else{
          for(int i =0;i<N;i++){
              cols[level] = i;
              if(isPromising(level)){
                  backTracking(level+1);
              }
          }
      }
  }
  public boolean isPromising(int level){
      for(int i=0;i<level;i++){
          if(cols[i]-cols[level]==0 || (Math.abs(cols[i] - cols[level]) - Math.abs(i - level)) ==0){
              return false;
          }
      }
      return true;
  }
}