프로그래머스 N-Queen

문제 

대표적인 백트래킹 문제인 n-queen이다

n개의 퀸이 n*n의 체스 판에서 서로 공격하지 못하는 경우의 수를 구하면 된다

 

내 풀이

우선 퀸이 서로 공격하지 못하려면 퀸은 서로 같은 열 같은 행,  같은 대각선에 존재하면 안 된다.

• 같은 행 : dfs의 depth로 사용하여 한 행에 하나의 퀸만 존재하게 했다.
• 같은 열 : dfs를 진행하며 board에 저장된 열의 값을 이용하여 같은 값이 존재하는지 체크하였다.
• 같은 대각선 :  같은 대각선에 존재하면 기울기가 1인 것임을 이용하여 같은 대각선내에 존재하는지 체크하였다.

 

백트래킹을 결정하는 함수

퀸이 같은 열이나 대각선에 위치하는 경우 DFS 진행을 멈추게 한다.

const isPossible = (row , board) => { // 같은 행 , 열 대각선에 없어야함
    for(let i = 0 ; i < row ; i++){
        if(board[i] === board[row]){
            return false
        } 

        if(Math.abs(row - i) === Math.abs(board[row] - board[i])){ //대각선에 있으면
           //기울기가 1임을 이용
           return false;
        }
    }

    return true
}

 

 

DFS를 실행하는 함수

각 행에서 가능한 모든 열에 퀸을 배치해보며 DFS를 진행한다.

• 특정 열에 퀸을 배치한 후, 배치 가능 여부를 확인하고 가능하다면 다음 행을 재귀 호출하여 DFS를 진행
• 모든 퀸이 배치된 경우(행이 체스판의 길이와 같은 경우), 경우의 수를 증가

const n_queen = (n , row , board) => {
    if(row === n ){
        count ++;
        return 
    }

    for(let i = 0 ; i < n ; i++){
        board[row] = i;
        if(isPossible(row ,board)){
            n_queen(n,row+1 , board)
        }
    }
}

전체 코드

function solution(n) {
    let count = 0; 
    const board = Array.from({length : n},_=> null);

    const isPossible = (row , board) => { // 같은 행 , 열 대각선에 없어야함
        for(let i = 0 ; i < row ; i++){
            if(board[i] === board[row]){
                return false
            } 
            
            if(Math.abs(row - i) === Math.abs(board[row] - board[i])){ //대각선에 있으면
               //기울기가 1임을 이용
               return false;
            }
        }
        
        return true
    }
    
    const n_queen = (n , row , board) => {
        if(row === n ){
            count ++;
            return 
        }
        
        for(let i = 0 ; i < n ; i++){
            board[row] = i;
            if(isPossible(row ,board)){
                n_queen(n,row+1 , board)
            }
        }
    }
    
    n_queen(n, 0, [...board])
    return count;
}

 출처 : 프로그래머스

문제 링크  : https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스