[프로그래머스] N-Queen - Javascript

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

 

문제 요약 :

1. n*n의 체스판에서 n개의 퀸이 서로 공격할 수 없게 배치하는 경우의 수

 

문제 풀이 시간 : 30분

문제 성공 여부 : 성공

 

접근 방법(성공) :

1. 2차원 배열을 만든다(체스판)
2. dfs(백트래킹)을 통해 둘 수 있는 모든 경우의 수를 파악한다.

이런 체스판이 있으면 퀸은 열에 최대 하나밖에 둘 수 없다. ( 퀸은 가로, 세로, 대각선으로 이동 가능 )

 

따라서 열마다 한 개의 퀸을 두면서 해당 위치에 퀸을 둘 수 있는지를 계산하며 체스판을 채우면 된다.

 

예)

(0,0)에 퀸을 두고 다음 열로 이동한다.

(1,0)에 퀸을 둘 수 있는지 확인한다 -> (0,0)과 (0,1)에 퀸이 있는지 확인 -> 못 둔다! -> continue;

(1,1)에 퀸을 둘 수 있는지 확인한다 -> (0,0)과 (0,1), (0,2)에 퀸이 있는지 확인 -> 못 둔다! -> continue;

(1,2)에 퀸을 둘 수 있는지 확인한다 -> (0,1)과 (0,2), (0,3)에 퀸이 있는지 확인 -> 둘 수 있다! -> (1,2)에 퀸을 두고 다음 열로 이동

.

.

.

를 반복하면 모든 경우의 수를 파악할 수 있다!

 

전체 코드(성공) :

function solution(n) {
    const chess = Array.from({length:n}, ()=>Array(n).fill(false));
    let ans = 0;
    
    const dfs = (chess, n, idx) => {
        if(idx===n){
            ans++; // 경우의 수 하나 추가
            return;
        }
        
        for(let i=0; i<n; i++){
            if(!check(chess, n, idx,i)) continue; // 놓을 수 없으면 패스
            
            chess[idx][i] = true;
            dfs(chess,n,idx+1);
            chess[idx][i] = false;
        }   
    }

    const check = (arr, n, x, y) => {
        for(let i=0; i<x; i++){ // 위로
            if(arr[i][y]) return false;
        }
        
        let raw = x, col = y;
        while(raw>=0 && col>=0){ // 왼쪽 대각선 위
            if(arr[raw--][col--]) return false;
        }
        
        raw = x, col = y;
        while(raw>=0 && col<n){ // 오른쪽 대각선 위
            if(arr[raw--][col++]) return false;
        }
        return true;
    }

    dfs(chess,n,0);
    return ans;
}

 

 

추가 학습

검색해 보니, 내가 생각한 로직보다 훨씬 효율적인 방법을 발견했다.

 

난 이차원 배열을 통해 시뮬레이션에 가까운 접근을 시도했으나, 1차원 배열로도 충분히 해결가능했다!

 

[1,3,0,2]와 같은 일차원 배열이 있다.

이 배열은 다음과 같이 해석할 수 있다.

[0,1,0,0]

[0,0,0,1]

[1,0,0,0]

[0,0,1,0]

이처럼, 이전 인덱스들의 위치를 통해 현재 위치에 퀸을 둘 수 있는지 없는지를 알 수 있다.

 

예를 들어,

[1,3,0,?] 단계에서, 마지막 3번째 인덱스의 ?에 들어갈 수를 찾아보자

 

0일 경우,

먼저 1,3,0 중에서 같은 col에 있는 퀸이 있는지 찾아본다.

그렇다. 2번째 인덱스에 0번째 열에 퀸이 존재하므로 3번째 행의 0번째 열에는 퀸을 둘 수가 없다.

 

1일 경우도 마찬가지로 (0,1)에 퀸이 존재하므로 둘 수 없다.

 

2인 경우는 일단 같은 col에 존재하는 퀸은 없다.

이제 대각선에 퀸이 존재하는지를 확인해봐야한다.

 

(x, y)과 (a, b)가 대각선에 위치하는지 아는 법은 간단하다.

(x-a)와 (y-b)의 절댓값이 서로 같으면 대각선이다!

 

따라서 해당 여부를 판단한 후 퀸을 놓아주면 보다 효율적으로 문제를 풀이할 수 있다!

 

출처 : https://supersfel.tistory.com/entry/JS-N-Queen

[JS] N-Queen