N-Queen

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

- 나의 풀이

 

✅ 길이 n 인 정사각형에서 n개의 퀸 ➡︎ 한 줄에 하나의 퀸만 들어갈 수 있음

일차원 배열로 압축 가능 ➡︎ chessBoard = new int[n];

rowIndex 이해 위한 그림, 해당 주황 한줄에 하나의 Q만 들어갈 수 있음

 

 

chessBoard 압축 이해 위한 그림 설명

 

 

✅ 공격범위

• 가로, 세로
  • 1차원 배열로 chessBorad를 생각했기 때문에 가로는 생각X
  • chessBoard 가 [1, 3, 0, 1] 이라면, 아래 그림과 같이 세로로 공격당하게 됨

[1,3,0,1] 일 때, 세로로 공격당하는 Q

• 대각선
  • 대각선은 기울기가 1
  • y증가량 / x증가량 = 1 따라서,  x증가량 = y증가량
  • 절댓값 사용하여 |x1 - x2| = |y1 - y2|

 

 - 나의 코드

class Solution {
    private static int[] chessBoard;
    int answer = 0;
    
    public int solution(int n) {
        
    
        // 길이 n 인 정사각형에서 n개의 퀸 -> 한 줄에 하나의 퀸만 들어갈 수 있음
        //int[] chessBoard = new int[n]
        chessBoard = new int[n];
        
        backTracking(n, 0);
        
        return answer;
    }
    
    public void backTracking(int n, int rowIndex) {
        // 끝까지 도달
        if(rowIndex == n) {
            answer++;
            return;
        }
        
        for(int i=0; i<n; i++) {
            //퀸 위치 (rowIndex, i)
            chessBoard[rowIndex] = i;
            
            // 놓을 여부 flag 
            boolean flag = true;
            
            // 이전에 놓인 퀸과 비교
            for(int j=0; j<rowIndex; j++) {
                // 세로로 같은 위치
                if(chessBoard[rowIndex] == chessBoard[j]){
                    flag = false;
                }
                
                // 대각선에 위치
                if(Math.abs(rowIndex-j) == Math.abs(chessBoard[rowIndex]-chessBoard[j])){
                    flag = false;
                }
            }
            
            if(flag) {
                backTracking(n, rowIndex+1);
            }
            
        }
    }
}