🕊 Link

Lv3. N-Queens
https://programmers.co.kr/learn/courses/30/lessons/12952

🧑🏻‍💻 Code(javascript)

function solution(n) {
  let answer = 0

  const dsf = (board, row) => {
    if (row === n - 1) {
      answer++
    } else {
      for (let col = 0; col < n; col++) {
        board[row + 1] = col
        if (isValid(board, row + 1)) {
          dsf(board, row + 1)
        }
      }
    }
  }
  const isValid = (board, newRow) => {
    for (let i = 0; i < newRow; i++) {
      if (board[i] === board[newRow]) return false
      if (Math.abs(i - newRow) === Math.abs(board[i] - board[newRow])) return false
    }
    return true
  }

  for (let col = 0; col < n; col++) {
    const board = new Array(n).fill(0)
    board[0] = col
    dsf(board, 0)
  }

  return answer
}

💡 Solution

function solution(n) {
  let answer = 0

  const dsf = (board, row) => {
    if (row === n - 1) {
      answer++ 
      // row와 n-1이 같은 경우는 모든 row에 말이 놓인 상황임
      // 아래에서 말을 놓은 후 isValid로 이미 검증까지 되어 있기 때문
    } else {
      // row가 n-1과 같지 않은 경우
      // 다음 줄(row+1)에 col을 0 ~ n-1까지 넣어보고
      // isValid로 검증해보고, 타당하면 dsf를 수행
      for (let col = 0; col < n; col++) {
        board[row + 1] = col
        if (isValid(board, row + 1)) {
          dsf(board, row + 1)
        }
      }
    }
  }
  const isValid = (board, newRow) => {
    // 위 그림의 경우에서 isValid에 들어왔다고 가정하면,
    // board [1, 3, 0], newRow=2(col=0)
    for (let i = 0; i < newRow; i++) {
      // board의 0번째 row부터 newRow-1번째 row까지 돌면서 그 값을 비교
      if (board[i] === board[newRow]) return false
      // 두 지점이 있을 때, 
      // 각 지점의 열의 차, 행의 차를 계산하여 그 값이 같은 경우
      // 두 지점은 한 대각선 안에 있음을 의미함.
      if (Math.abs(i - newRow) === Math.abs(board[i] - board[newRow])) return false
      // |기존 row의 행(i) - 신규 row의 행(newRow)| 
      // |기존 row의 열(board[i]) - 신규 row의 열(board[newRow])|
      // 기존 row의 행(i) 
      // 기존 row의 열(board[i])
      // 신규 row의 행(newRow)
      // 신규 row의 열(board[newRow])
    }
    return true
  }

  // 여기서의 for 반복문은 첫번째 row에서 어떤 col을 선택할 것인지에 대한 loop
  // 즉, row[0]에 col=0, col=1, col=2, col=3을 대입하고 dsf를 수행함
  for (let col = 0; col < n; col++) {
    // board's index = row
    // board's value = col
    const board = new Array(n).fill(0)
    board[0] = col
    dsf(board, 0)
  }

  return answer
}

👨🏻‍💻💭 Self Feedback

같은 대각선 상에 있는지 확인하는 로직에서 두 로직이 헷갈려 오래 고민함
if (Math.abs(i - newRow) === Math.abs(board[i] - board[newRow])) return false
if (Math.abs(i - board[i]) === Math.abs(newRow - board[newRow])) return false
각 지점의 행과 열을 계산해서 비교하는 것이 아니라
각 지점의 행끼리, 열끼리 계산해서 비교해야 함

📚 참고
[프로그래머스] LV.3 N-Queen (JS) by.longroadhome

• 2021.08.29 - 최초 작성

댓글 환영 질문 환영 by.protect-me