[JS|백트래킹] 프로그래머스 12952번. N-Queen

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

---

 

1. 입력과 출력

• 입력
  
  • 체스판의 가로,세로의 길이 n
• 출력
  
  • n개의 퀸이 조건에 만족하도록 배치할 수 있는 경우의 수 return

 

2. 문제 풀이 로직

해당 문제는 체스판의 가로,세로 길이인 n이 들어올 때, 퀸을 n개 놓을 수 있는 경우가 몇 가지인지 알아보는 문제이다.

(닌텐도 레이튼 교수 시리즈를 좋아하는 사람에겐 익숙한 문제이다!)

 

 

Queen의 활동 범위는 다음과 같다.

Queen을 놓은 곳의 같은 행과 열, 그리고 대각선에는 Queen을 놓을 수 없다.

 

 

체스판에 N개의 Queen을 둘 수 있는 경우는 '백트래킹'을 사용하여 찾을 수 있다.

 

즉, Queen을 둘 때마다 해당 위치가 놓을 수 있는 자리인지 확인하면 된다.

⇩

1. 같은 행에 Queen이 없어야 함

2. 같은 열에 Queen이 없어야 함

3. 대각선에 Queen이 없어야 함

 

위 조건을 모두 통과한 자리라면 Queen을 놓고,

다음 행으로 넘어가서 똑같이 Queen을 놓기 전 조건을 확인하며

마지막 행까지 무사히 Queen을 놓았다면 경우의 수를 +1 하여 업데이트 한다.

 

---

 

 

그럼 이제 코드,그림과 함께 조건을 확인하는 방법에 대해 알아보자.

 

① 같은 행에 Queen이 없어야 함

 

같은 행에 2개 이상의 Queen을 놓지 않기 위해서는 행(row)를 기준으로 코드를 진행하면 된다.

즉, row에 Queen을 놓으면 row + 1를 통해 다음 행으로 넘어간다.

 

이를 코드와 표현하면 다음과 같다.

function solution(n) {
  const checkBoard = []
  let answer = 0

  // 열/대각선 확인하기
  function checking(row) {
    // queen을 놓을 수 있는 자리인지 확인하는 함수
  }

  // 백트래킹 함수
  function backtracking(row) {
    // 1-4. 행 번호가 n이라면 -> queen을 n개 놓았다면
    if (row == n) {
      return answer++ // 경우의 수를 업데이트 한다.
    }


    for (let queen = 0; queen < n; queen++) {
      // 조건 1. 같은 행에 Queen이 없어야 함.
      checkBoard[row] = queen // 1-1. 해당 행에 queen을 놓는다. 
      if (checking(row)) { // 1-2. 만약 queen을 놓을 수 있는 자리라면
        backtracking(row + 1) // 1-3. 다음 행으로 넘어간다.
      }
    }
    return
  }

  backtracking(0) // 1-0. 인덱스 0번 행부터 진행한다.
  return answer
}

console.log(solution(4)) // 2

 

1-0. 인덱스 0번 행부터 시작한다.

1-1. 해당 행에 queen을 놓는다. (이때 queen은 열 번호와 같다. 이에 대해서는 조건 2번에서 설명한다.)

 

1-2. 만약 queen을 놓을 수 있는 자리라면

       1-3. 다음 행(row +1)으로 넘어간다.

1-1. queen을 놓을 수 없는 자리라면 해당 행의 다음 열 번호(for문 queen+1)에 queen을 놓는다.

 

1-4. 행 번호가 n이 될 때까지 즉, 마지막 행에 queen을 놓을 때까지 backtracking 함수를 진행한다.

 

 

그림으로 보면 다음과 같다.

 

 

 

 

② 같은 열에 Queen이 없어야 함

열과 대각선의 경우 다음 함수를 통해 확인한다.

  // 열/대각선 확인하기
  function checking(row) {
    for (let i = 0; i < row; i++) {
      if (
        checkBoard[row] == checkBoard[i] ||
        Math.abs(row - i) == Math.abs(checkBoard[row] - checkBoard[i])
      ) {
        return false
      }
    }
    return true
  }

 

다음 함수에서 사용한 checkBoard는 1차원 배열이다.

 

실제 체스판과 같은 모양이 아닌 1차원 배열로 열/대각선의 조건을 통과한 자리인지 확인하는 방법은 다음과 같다.

 

 

즉, 해당 열에서 Queen을 놓을 때, checkBoard에 이미 해당 열의 번호가 있다면 다음 열로 넘어간다.

  // 열/대각선 확인하기
  function checking(row) {
    for (let i = 0; i < row; i++) { // i는 열의 번호와 같다.
      if (checkBoard[row] == checkBoard[i]) { // 이미 해당 열의 번호가 있다면
        return false // 놓을 수 없는 자리!
      }
    }
    return true // 해당 열의 번호가 없다면 놓을 수 있는 자리!
  }

 

 

③ 대각선에 Queen이 없어야 함

같은 대각선에 있는 자리인지 확인하기 위해서 어떤 방법을 쓸 수 있을까?

단순히 For문을 돌면서 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단의 대각선을 확인하기에는 비효율적이다.

 

대각선이라는 것은 가로 길이와 세로 길이의 차이가 절댓값으로 같다는 것을 의미한다.

글로만 보면 이해가 되지 않으니 그림을 통해 알아보자.

 

 

 

이미 알고 있는 가로와 세로의 길이를 통해 이전에 놓았던 Queen들이 대각선에 위치해있는지 확인할 수 있다.

  function checking(row) {
    for (let i = 0; i < row; i++) {
	  // 만약 대각선에 Queen이 있다면 
      if (Math.abs(row - i) == Math.abs(checkBoard[row] - checkBoard[i])) {
        return false // 놓을 수 없는 자리!
      }
    }
    return true // 대각선에 Queen이 없으므로 놓을 수 있는 자리!
  }

 

 

3. 전체 코드

해당 조건 확인과 백트래킹을 사용한 전체 코드이다.

function solution(n) {
  const checkBoard = []
  let answer = 0

  // 열/대각선 확인하기
  function checking(row) {
    for (let i = 0; i < row; i++) {
      if (
        checkBoard[row] == checkBoard[i] ||
        Math.abs(row - i) == Math.abs(checkBoard[row] - checkBoard[i])
      ) {
        return false
      }
    }
    return true
  }

  // 백트래킹 함수
  function backtracking(row) {
    if (row == n) {
      console.log(checkBoard)
      answer++
      return
    }

    for (let i = 0; i < n; i++) {
      checkBoard[row] = i
      if (checking(row)) {
        backtracking(row + 1)
      }
    }
    return
  }

  backtracking(0)
  return answer
}
console.log(solution(4)) // 2