Portfolio

📄문제

✏️풀이

재영

제 기준은 기능에 따라 4개의 함수를 필요로 함니다.

solveNQueens: 메인 함수. 조건에 맞는 결과 퉤!

check: 가지를 칠지 말지 결정!

makeQueenMap: 리턴 값에 맞게 맵을 만들고 반환!

backTracking: res를 만들도록 백트래킹 구현, res 반환!

일단 결국 Queen이 움직이는 건 행/열/대각선. 이러한 변수들을 조금이라도 줄이고자 저는 cols라는 배열로 queen의 위치를 저장했어유.

만약 cols의 length가 n개라면, 실제 queen도 n의 행까지 채웠다!는 것을 의미하쥬. 그러면 이제 행은 무시해도 돼유. 배열 길이로 고려했기에 절대 겹칠 수가 없으니까유.

그리고 cols의 특정 인덱스 값이 y라면, 이제 y는 더이상 못 씀니다. 그러면 이제 우리는 열 조건까지 고려했어유.

그렇다면 결과적으로, 우리는 이제 대각선을 고려해야 하는데, 행간 길이 차이 === 열간 길이 차이를 만족하면 대각선 위치에 놓인 거에유. 자, 이렇게 조건을 비교하는 check는 완료했어유.

그래프를 잘 꾸며줍시다. makeQueenMap에 대한 설명은 생략할게유! (그저 조건에 맞게)

만약 이제 체크를 한 상태에서 cols.length === n이라면, 결국 queen을 마지막 행까지 채웠단 거쥬. 따라서 res에 추가해줍니당.

그럼 이제 끝났어유! 반환되는 값에 따라 res를 업데이트 해주면 됩니당.


const makeQueenMap = (n, cols) => {
	// 2차원 배열을 만든다.
  const arr = Array.from({length: n}, () => new Array(n).fill('.'));
	
	// Queen을 놓아준다.
  cols.forEach((y, x) => {
    arr[x][y] = 'Q';
  })
	// 조건에 맞게 1차원 배열로 변환시켜준다.
  return arr.map(innerArr => innerArr.join(''));
}

// 조건은 다음과 같다.
const check = (cols) => {
	// 배열의 길이다. (즉, 현재까지 처리된 행 수를 의미할 것이다)
  const arrLength = cols.length;
	// 만약 배열의 길이가 2보다 작으면, 결과적으로 비교할 queen이 없다는 거다. true.
  if (arrLength < 2) return true;
	// cols는 얕은 복사를 해준다. 그래야 영향을 미치지 않는다. (called by ref)
  const nowCols = [...cols];
	// 마지막 행을 비교하기 위해 이렇게 빼준다.
  const lastCol = nowCols.pop(); 
	// 이전의 행들의 퀸이 움직일 수 있는 값에 포함되지 않는지를 체크한다.
  return nowCols.every((nowCol, idx) =>
		// 같은 열이 아닐 때
		// 그리고 행 값 차이 = 열 값 차이가 아닐 때 (대각선 특징) 
    nowCol !== lastCol 
    && Math.abs(nowCol - lastCol) !== Math.abs(arrLength - 1 - idx)
  );
}

// n: 문제에서 설정된 값
// cols: 현재 사용된 열들을 행의 인덱스에 매칭되어 값을 설정
// res: 결과 값을 담은 배열
const backTracking = (n, cols, res) => {
	// 가지치기 -> 만약 현재 조건을 만족하지 못한다면 `res`를 반환한다.
  if (!check(cols)) return res;
	// 조건은 이제 통과. 만약 끝까지 다 갔고, 퀸을 있는 만큼 채웠다면,
	// `res에 `makeQueenMap`으로 만든 맵을 넣어 반환한다.
  if (cols.length === n) return [...res, makeQueenMap(n, cols)];

	// 아직 다 못 채웠다면 여기서 for문을 돌린다. 이때, 다시 재귀를 시키는데,
	// for문을 돌렸기 때문에 일단 '어느 행에 놓을 것인지'에 대한 문제는 해결했다. 
  // 다음 퀸의 열 값을 찾는 문제로 집중하자.
	// 따라서 현재 열 값을 `cols`에 넣어 재귀함수를 호출한다.
  for (let i = 0; i < n; i += 1) {
    res = backTracking(n, [...cols, i], res);
  }
	
	// 호출된 backTracking의 res값을 리턴해준다.
  return res;
}

const solveNQueens = n => backTracking(n, [], []);

//84ms

은찬


const solveNQueens = (n) => {
    const answer = [];
    let board = Array.from({length: n}, () => Array(n).fill("."));
    
    const isPossible = (x, y) => {
        //up
        for(let i = x - 1; i >= 0; i--){
            if(board[i][y] === "Q"){
                return false;
            }
        }
        
        //down
        for(let i = x + 1; i < n; i++){
            if(board[i][y] === "Q"){
                return false;
            }
        }
        
        //left
        for(let i = y - 1; i >= 0; i--){
            if(board[x][i] === "Q"){
                return false;
            }
        }
        
        //right
        for(let i = y + 1; i < n; i++){
            if(board[x][i] === "Q"){
                return false;
            }
        }
        
        //upper left
        for(let i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //upper right
        for(let i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //lower left
        for(let i = x + 1, j = y - 1; i < n && j >= 0; i++, j--){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //lower right
        for(let i = x + 1, j = y + 1; i < n && j < n; i++, j++){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        return true;
    }
    
    const dfs = (x, queen) => {
        if(!queen){
            answer.push(board.slice().map(b => b.join("")));
            return;
        }
        
        for(let j = 0; j < n; j++){
            if(isPossible(x, j)){
                board[x][j] = "Q";
                dfs(x + 1, queen - 1);
                board[x][j] = ".";
            }
        }
    };
    
    dfs(0, n);
    
    return answer;
};

가영


var solveNQueens = function(n) {
    const answer = [];
    const arr = new Array(n);
    
    const getQueen = (depth, queens) => {
        if (depth === n) {
            answer.push(queens);
            return;
        }

        for (let i = 0; i < n; i++) {
            arr[depth] = i;

            if (isPossible(depth)) {
                let queen = '';
                for (let j = 0; j < n; j++) {
                    queen += i === j ? 'Q' : '.';
                }
                getQueen(depth + 1, [...queens, queen]);
            }
        }
    }

    const isPossible = (depth) => {
        for (let i = 0; i < depth; i++) {
            if (arr[depth] === arr[i]
               || Math.abs(depth - i) === Math.abs(arr[depth] - arr[i])) {
                return false;
            } 
        }
        return true;
    }
    
    getQueen(0, []);

    return answer;
};

N-Queens

📄문제

✏️풀이