[프로그래머스] N-Queen (Java)

프로그래머스 N-Queen

문제풀이

백트래킹의 기본 예제로 사용되는 N-Queen 문제다.

• col 배열은 i행에는 col[i]열에 퀸이 배치되어있음을 나타낸다.
• isPossible 함수
  • 행을 중심으로 퀸을 배치해나가기 때문에 현재 행의 이전 행들 중에서 같은 열에 퀸이 배치된적이 있는지 확인한다. (행, 열 확인)
  • 두 퀸 사이의 거리를 비교했을 때 행의 증가량과 열의 증가량이 같으면 대각선이다. (대각선 확인)

구현코드

import java.util.*;

class Solution {
    
    static int[] col;
    static int answer;
    
    public int solution(int n) {
        answer = 0;
        
        for(int i = 0 ; i < n ; ++i) {
            col = new int[n];
            col[0] = i;
            backtracking(n, 1);
        }
        
        return answer;
    }
    
    private void backtracking(int max, int row){
        if(row == max){
            answer++;
            col[row - 1] = 0;
            return;
        }
        
        for(int i = 0 ; i < max ; ++i){
            col[row] = i;
            if(isPossible(row)){
                backtracking(max, row + 1);
            } else {
                col[row] = 0;
            }
        }
        col[row] = 0;
    }
    
    private boolean isPossible(int row){
        for(int i = 0 ; i < row ; ++i){
            if(col[i] == col[row]) return false;
            if(Math.abs(row - i) == Math.abs(col[row] - col[i])) return false;
        }
        
        return true;
    }
   
}