[Programmers] N-Queen - JavaScript

Joosi_Cool·2023년 5월 6일
1

Programmers

목록 보기
81/98
post-thumbnail

문제설명

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

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

Imgur
Imgur

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

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

입출력 예
n result
4 2
입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges



설계 과정

우선 함수를 2개 만들어야한다.
1. possibleFun(board,row) 를 받으면 아래과정 시행
-> 같은 라인이나 대각선에 있다면 false
그게 아니라면 true
여기서 같은 대각선은 절댓값 기준으로 지금 행렬의 행 - 다른 행 === 지금 행렬의 열 - 다른 행 이 같으면 기울기가 -1 혹은 1이 되기 때문에 같은 대각선에 있는 것이다.
2. dfs(board, row)
이 값을 받았을때 row===n으로 가게 되면 성공으로 answer++
아니라면 1부터 n까지 다음행에 값을 하나씩 넣어주면서 possibleFun에 넣으면서 가능성을 체크하고 true라면 재귀 실행

  • 위의 두함수를 가지고 아래를 해보자.
    1부터 n까지 board에 첫번째 값을 다르게 한 다음에 dfs(board, row)넘겨주면서 answer을 더해준다.


정답 코드

function possibleFun(board,row){
    //전부터 같은 라인 혹은 대각선에 있는지 체크
    for(var i = 1;i<row;i++){
        // 같은 라인에 있는지 체크
        if(board[i]===board[row]){
            return false;
        }
        // 같은 대각선에 있는지 체크
        if(Math.abs(board[i]-board[row])===Math.abs(i-row)){
            return false;
        }
    }
    return true;

}


function solution(n) {
    var answer = 0;
    function dfs(board, row){
        if(row===n){
            answer++;
        }
        else{
             // row에 무슨 열에 값을 넣을껀지 정함
            for(var i = 1;i<=n;i++){
                board[row+1] = i;
                if(possibleFun(board,row+1)){
                    dfs(board,row+1);
                }
            }
        }
       
    }

    for(var i =1;i<=n;i++){
        var board = new Array(n+1).fill(0);
        board[1] = i;
        dfs(board,1);
    }

    return answer;
}


결과



profile
집돌이 FE개발자의 노트

1개의 댓글

comment-user-thumbnail
2023년 5월 7일

깔끔한 풀이 잘 보고 갑니다 !

답글 달기