Portfolio


// 2차원 배열을 사용하여 풀이하지 않아도 된다.
// 2차원 배열을 체스판으로 생각했을 때 첫번째 라인에 퀸이 위치하게 되면, 해당 라인의 가로 세로는 어떠한 퀸도 위치할 수 없다.
// -> 1차원 배열의 index를 체스판의 가로, 값을 세로라인으로 볼 수 있다.

function solution(n) {
    let answer = 0;
    
    const dfs = (board, row) => {
        if(n === row) answer ++; // 현재 행과 n이 같다는 것은 체스판을 다 돌고 동시에 4개의 퀸도 배치했다는 뜻이니 1 증가
        else {
            for(let i = 1; i <= n; i ++){
                board[row+1] = i; // 다음 라인에 퀸을 배치하고
                // isValid 라는 함수를 통해 해당 위치 퀸이 유효한지 검사
                // 유효하다면 다음 위치를 계속 탐색
                if(isValid(board, row+1)) dfs(board, row+1);
            }
        }
    }
    
    const isValid = (board, row) => {
        for(let i =1; i < row; i ++){
            // 같은 라인에 있는 경우 배치 불가
            if(board[i] === board[row]) return false;
            
            // 대각 라인에 있는 경우 배치 불가
            if(Math.abs(i-row) === Math.abs(board[i] - board[row])) return false;
        }
        // 위 조건을 모두 통과하면 배치 가능
        return true;
    }
    
    for(let i = 1; i <= n; i++){
        const board = new Array(n+1).fill(0);
        board[1] = i; // 체스판의 첫번째 세로라인 중 i칸에 퀸을 배치
        dfs(board, 1); // 배치가 완료된 체스판과 현재 세로라인인 1을 dfs 함수에 전달
    }
    return answer
}


// 레벨은 2로되어있는데 왜 체감은 레벨 4죠....?😭😭😭
// 문제를 이해하는데에도 너무 많은 시간이 걸려서 검색의 힘을 빌렸습니다..
// 문제해결보다는 로직에 대한 이해를 한다고 생각하고 해설을 긁어왔습니다.
function solution(n) {
  let answer = 0;
	// 입력 받은 n만큼의 1차원 배열을 만들고 방문하지 않았다는 의미로 상수를 넣어줍니다.  
  const NOT_VISITED = 100;
  const status = Array(n).fill(NOT_VISITED);

  const isAvailable = (status, row, col) => {
		// 이미 방문한 노드라면 함수의 실행을 종료합니다.
    if (status[col] !== NOT_VISITED) return false;
		// 방문하지 않은 노드라면 배열의 길이만큼 반복문을 돌며 대각선과 
		// 세로에 퀸이 존재하는지 확인 후 존재한다면 현재위치에 퀸을 놓을 수 없다고 판단
    // false를 return 하고 존재하지 않는다면 퀸을 놓을 수 있다고 판단하여 true를 return 해줍니다.
    for (let idx = 0; idx < status.length; idx++) {
      if (Math.abs((row - status[idx]) / (col - idx)) === 1) {
        return false;
      }
    }
    return true;
  };
	// 매개변수인 row값이 n과 같아지면 함수가 종료됩니다.
	// 0부터 n - 1행까지 모두 퀸이 채워지면 경우의 수(answer)를 1 더해줍니다.
  const dfs = (n, row, status) => {
    if (row === n) {
      answer ++;
      return;
    }
		// n만큼 반복문을 동며 현재 위치에 퀸을 놓을 수 있는지 확인해준다.
		// 놓을 수 있다면 자리에 row값을 기록하고 재귀를 통해 row에 1을 더한 후 
		// dfs함수를 실행한다.
    for (let col = 0; col < n; col++) {
      if (isAvailable(status, row, col)) {
        status[col] = row;
        dfs(n, row + 1, status);
        status[col] = NOT_VISITED;
      }
    }
  };

  dfs(n, 0, status);

  return answer;
}


function isOnDiagonal(a,b){
    //a=[ax,ay] ,b=[bx,by]로 각 
    // x=|ax-bx| , y= |ay-by|;
    const [ax,ay]=a, [bx,by]=b;
    const x =Math.abs(ax-bx);
    const y=Math.abs(ay-by);
    return x===y? true: false // 같은 값이면 대각선상에 있는것으로 true 반환,  아니다면 false 반환
}


function solution(n) {

    //nxn 인 체스판, 퀸은 서로 같은 가로줄, 세로줄, 대각선에 있으면 안된다. 
    //board 배열에서 가로를 각 인덱스로 표현, 각 인덱스에 할당되는0,1,2,3,4...n 이 세로 줄 표현 
    // 대각선은  x,y 가 있을 때, |x행 - y행|==|x열 - y열| 각은 대각선상에 있는 것으로 생각한다. 
    // 우선 각 숫자를 체워지고 대각선 검사 

    let cnt=0;
    // 대각선 체크
    function DFS(board, depth){
        if(depth ===n){
            cnt++
        }else{
            for(let i =0 ;i<n; i++){
                if(!board.includes(i)){
                    board[depth]=i;
                    let flag= false;
                    //현 depth만 검사를 해주면 ok;
                    for(let i =0; i<depth; i++){
                        if(isOnDiagonal([i,board[i]],[depth, board[depth]])){
                            board[depth]=null;
                            flag= true;
                            break
                        }
                    }
                    if(flag)continue;
                    DFS(board,depth+1);
                    board[depth]=null;
                }
            }
        }
    }

    const board=Array.from({length:n}).fill(null);
    DFS(board, 0 );
    return cnt
}


// 계속 고민하다가 결국 강사님 코드를 거의 그대로 따라 적었습니다 ㅜ.ㅜ
// 재귀적으로 사고하는게 쉽지 않네요 ...!!!!

function check(queen, row) {
    for (let i = 0; i < row; i++) { // 이전 row까지 겹치는 열이 있거나, 대각선에 위치하고 있는지 살핀다.
        if (queen[i] == queen[row] || Math.abs(queen[i] - queen[row]) == row - i) {
            return false; // 이전 row와 대각선 또는 세로에 위치한 경우 퀸을 둘 수 없다.
        }
    }
    return true;
}

function search(queen, row) { // 행마다 퀸을 둘 수 있는지 살핍니다.
    const n = queen.length;
    let count = 0;
    
    if (row == n) return 1; // 마지막 row까지 통과됐다면 1을 count에 더하게 된다.
    
    for (let col = 0; col < n; col++) {
        queen[row] = col; //row행의 col열에 퀸 둬본다.
        if (check(queen, row)) { // 퀸을 둘 수 있다면
            count += search(queen, row + 1); // 다음 row
        } // 퀸을 둘 수 없다면 다음 col에 퀸을 둬본다.
    }
    return count;
}

function solution(n) {
    const answer = search(new Array(n).fill(0), 0); // 0행부터 시작
    return answer;
}


function solution(n) {
    let answer = 0;
    const arr = Array(n).fill().map(() => Array(n).fill(0)); //퀸을 둘 수 있는 곳은 arr[y][x] = 0인곳!
    const col = Array.from({length : n}, () => false); //퀸 위치의 세로줄에는 퀸을 놓을 수 없습니다.
    // 윗 방향 볼 필요없습니다!
		// 아래 오른쪽 대각선, 아래 왼쪽 대각선만 고려해줍니다.
    const d = [[1, 1], [1, -1]];
    
		// 퀸을 놓을 수 없는 곳을 마킹하는 함수입니다.
		// 처음에 카운트말고 true, false로 했다가 마킹이 풀려선 안되는 곳이 false가 되어버려서
		// 0이상의 값을 저장하도록 변경했어요
		// 만약 arr[y][x] = 2 라면 해당 위치는 2개의 퀸에 의해 놓을수 없는 위치란 뜻입니다.
    function marking(mark, y, x){
        arr[y][x] += mark;
        for(let [dy, dx] of d){
            let ny = y + dy;
            let nx = x + dx;
            while(ny < n && ny >= 0 && nx < n && nx >= 0){
                arr[ny][nx] += mark; //마크가 1이면 마킹, -1이면 마킹 해제
                ny += dy;
                nx += dx;
            }
        }
    }
    
		// 퀸은 반드시 하나의 가로줄에 하나의 퀸만 존재해야 합니다.
		// 따라서 하나의 가로줄에 퀸을 놓았다면 나머지 옆칸은 신경 X, 다음 줄로 넘어갑니다.
    function DFS(cnt, y){
        if(y >= n){
            if(cnt === n) answer += 1;
            return;
        }
        
				// i는 x좌표를 의미합니다.
				// 하나의 세로줄에 이미 퀸이 있거나 대각선에 의해 퀸을 놓을 수 없다면 패스합니다.
        for(let i = 0; i<n; i += 1){
            if(!col[i] && !arr[y][i]){
                col[i] = true;
                marking(1, y, i); // 1증가
                DFS(cnt + 1, y + 1); // 퀸을 놓고 다음 가로줄로 이동합니다.
								// 퀸을 다시 지워줍니다.
                col[i] = false;
                marking(-1, y, i); // 1감소
            }
        }
    }
    
    DFS(0, 0);
    
    return answer;
}


function isValid(chess, row) {
  let n = chess.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (chess[i][j] === 0) continue;

      //너무 복잡해져서 여기서 포기했습니다.
    }
  }
  return true;
}

function findLocation(chess, row) {
  let cnt = 0;

  for (let i = 0; i < chess.length; i++) {
    chess[row][i] = 1;

    if (isValid(chess, row)) {
      if (row === chess.length - 1) {
        cnt += 1;
      } else {
        cnt += findLocation(chess, row + 1);
      }
    }
    chess[row][i] = 0;
  }
  return cnt;
}

function solution(n) {
  const chess = Array.from({ length: n }, () => [0, 0, 0, 0]);
  return findLocation(chess, 0);
}


function solution(n) {
  let cnt = 0;

  //1차원 배열로 생각할 수 있음 (index= 행, value = 열)
  //처음으로 놓는 퀸의 열값 저장. 행 index = 1
  for (let i = 1; i < n + 1; i++) {
    let chess = Array.from({ length: n + 1 }, () => 0);
    chess[1] = i;
    locateQueen(chess, 1);
  }

  return cnt;

  //퀸의 배치 조건을 검사를 하는 함수
  function isValid(chess, row) {
    for (let i = 1; i < row; i++) {
      if (chess[i] === chess[row]) {
        //열이 같을 때 false
        return false;
      }
      if (Math.abs(i - row) === Math.abs(chess[i] - chess[row])) {
        //대각선에 위치할 때 false(풀이참고함)
        return false;
      }
    }
    return true;
  }

  function locateQueen(chess, row) {
    //console.log(chess, row, chess.length - 1);
    //마지막 행까지 퀸이 배치됐다면 경우의 수 추가
    if (row === chess.length - 1) {
      cnt += 1;
    } else {
      //다음 행의 열을 순회하기
      for (let i = 1; i < chess.length; i++) {
        chess[row + 1] = i;
        //만약 해당 열에 퀸을 추가 가능하면 다음 행으로 넘어감
        if (isValid(chess, row + 1)) {
          locateQueen(chess, row + 1);
        }
      }
    }
  }
}

N-Queen

풀이