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

# 문제 원문

 

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

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

 

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

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

입출력 예

n / result

4

2

 

# 문제 풀이

 

백트래킹을 대표하는 문제중 하나로 볼 수 있는 체스판 위의 퀸을 찾는 문제이다. 개인적으로 DFS 를 이용해서 1차원 배열로 문제에 접근했다. DFS로 입력 받은 N에 맞게 NxN 크기의 체스판 위의 N개의 퀸이 있을 수 있는 모든 조합을 구했고, 그걸 백트래킹 방법으로 필터링해서 문제에 부합하는 방법들의 갯수를 구해서 반환했다. 솔직히 1차원 배열을 이용한 조합을 구하는 것은 조건 자체가 같은 열과 행에 무조건 하나의 퀸만 있을 수 있으니 그렇게 어렵지 않았지만 필터링 하는 방법에 대해서는 그 규칙을 찾기가 조금 어려워서 팁을 보고 도움을 받았다. (기울기에 대한 수학적 공식이 필요하다). 기본에 충실하면서도 어려운 문제다.

 

# 솔루션 플로우

1. 입력 받은 N 길이의 1차원 배열 arr를 구한다.(요소는 0, ...N로 이루어져있다.)

2. arr를 통한 재귀 DFS를 시작한다.

3. arr의 각 요소를 하나씩 stack에 push하고 재귀를 진행한 후 하나씩 제거한다.

4. stack의 내용물이 과 현재 arr의 current가 서로 대각선상에 있지 않은지 확인한다.

5. 서로 대각선에 없다면 DFS를 계속하고 아니라면 이전 단계로 돌아간다.

6. stack의 length가 입력 받은 N에 부합한다면 모든 퀸이 적절한 위치에 배치되었다는 것이니 result에 push 해준다.

7. 얻어진 result의 length를 반환한다.

1. 재귀함수 를 활용한 풀이

function solution(n) {
    const result = [];
    const arr = Array.from({ length: n }, (_, idx) => idx);

    const dfs = (arr, stack = []) => {
        if (stack.length === n) {
            result.push(Array.from(stack));
        }
        if (arr.length > 0) {
            arr.forEach((current, idx) => {
                const check = !Array.from(stack).some((prev, pdx) => {
                    if (Math.abs(current - prev) === Math.abs(pdx - stack.length)) {
                        return true;
                    }
                });
                stack.push(current);
                if (check) dfs([...arr.slice(0, idx), ...arr.slice(idx + 1, arr.length)], stack);
                stack.pop();
            });
        }
    }
    
    dfs(arr);

    return result.length;
}