[코딩테스트]백준 - N-Queen

N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

출처

• 문제를 만든 사람: baekjoon

해결한 코드

function b9663(){
  var fs = require('fs');
  var input = fs.readFileSync('/dev/stdin').toString().split('\n');
  // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split(' ')
  var n = parseInt(input[0])
  var queenArray = new Array(n).fill(0)
  // queen이 있는 '열'에 대한 배열
  // queenArray[x] = y => (x,y) 자리에 queen이 있다. 
  var count = []
  
  n_queen(0, count, n, queenArray)
  console.log(count.length)
}

function n_queen(row, count, n, queenArray){
  if(row == n){
    var str = ''
    for(var a=0; a<queenArray.length; a++){
      str += queenArray[a].toString()
    }
    count.push(str)
    return
  }
  
  for(var i=0; i<n; i++){
    queenArray[row] = i 
    // queen을 (row, i) 자리가 놓아봄 
    if(isPromising(row, i, queenArray)){
      // 유망성 검사 => (row, i) 자리가 ok면
      n_queen(row+1, count, n, queenArray)
      // 다음 행(row+1)에 대한 n_queen 진행
    }
  }
}

function isPromising(x, y, queenArray){
  for(var i=0; i<x; i++){
    if(queenArray[i] === y || Math.abs(x-i) === Math.abs(y-queenArray[i])){
      // 만약 이미 같은 행, 같은 열에 queen이 있다면 
      // 또는 대각선 위치에 queen이 있다면 
      return false
    }
  }
  return true 
}

b9663()

알고리즘

1. (0,0) 부터 (n,n) 까지 모든 자리에 대하여
2. 유망성 있는 자리인지 아닌지를 따진 후
3. 유망성 있는 자리인 경우만 재귀를 돌린다.

사실 처음엔 2차원 배열을 만들고, queen을 배치해나갈 때마다 "같은 행에, 같은 열에, 대각선에 퀸이 있는지" 검사하면서 진행하려고 했었다.

하지만 구글링을 통해 2차원 배열을 굳이 만들어 사용할 필요가 없음을 느꼈고...

1. 퀸을 배치한 '열'에 대한 배열을 만든다.

ex. queenArray[x] = y 일 때, 2차원 행렬 좌표 상에서 (x,y)에 퀸이 있다는 의미이다.

2. 백트래킹을 위한 재귀 함수를 만든다.

2-1. 재귀 함수에 필요한 변수는?
👉🏻 queenArray[x] = y의 x, n, queenArray, 퀸 배치 완료된 queenArray를 담을 배열
2-2. queenArray[x]에 0부터 n까지의 수를 넣어본다.
2-3. 유망성 검사를 한다. "queenArray[x]에 이 수를 넣어도 괜찮은가?"
2-4. 괜찮으면 다음 퀸 배치를 위해 x+1의 값으로 재귀를 돌린다.
2-5. 괜찮지 않으면?
👉🏻 0부터 n까지의 수를 넣어보는 단계로 돌아가겠지? 유망성 검사에서 탈락한 그 수의 다음 수에 대해서 검사할 것이다.

그럼 queenArray[0] 부터 queenArray[7]까지 알맞은 배열 원소를 넣기 위해 0부터 값을 넣어 유망성을 검사해보자.

3. 유망성 검사를 위한 함수를 만든다.

3-1. 퀸이 공격할 수 있는 자리는?

퀸은 같은 행, 같은 열, 대각선으로 공격할 수 있다.
따라서 다음에 배치할 퀸은 같은 행, 같은 열, 대각선에 위치해선 안된다.

3-2. queenArray[0] = 0에 대한 유망성 검사를 한다고 가정하면,

for(var i=0; i<0; i++)

이 부분에 들어가지 못하므로 return true가 되어 queenArray[0] = 0이 된다.
따라서 row+1하여 n_queen을 수행한다.

3-3. queenArray[1] = 0의 경우,
queenArray[0]이 이미 0이므로 false
queenArray[1] = 1의 경우, 좌표 (0,0)과 (1,1)이 대각선에 위치하여 안된다.
즉, x좌표값의 차(1-0) = 1, y좌표값의 차(1 - queenArray[0]) = 1로 서로 같으므로 false
queenArray[1] = 2의 경우, 현재 0~1까지 2인 값도 없고, 대각선 좌표에 해당하지 않으므로

return true가 된다. row+1을 하여 n_queen을 수행한다.

3-4. queenArray[2] = 0의 경우, queenArray에 이미 0값이 있으므로 안됨
queenArray[2] = 1의 경우, 좌표(2,1)과 (1,2)은 대각선에 위치하여 안된다.
x좌표값의 차(2-1) = 1, y좌표값의 차(1-2) = -1로, 각 절댓값이 서로 같으므로 false
queenArray[2] = 2의 경우, queenArray에 이미 2값이 있으므로 안됨
queenArray[2] = 3의 경우, 좌표(1,2)와 대각성에 위치하여 안된다.
queenArray[2] = 4의 경우, 현재 0~2까지 4인 값도 없고, 대각선 좌표에 해당하지 않으므로

return true가 된다. row+1을 하여 n_queen을 수행한다.

3-5. queenArray[3] = 0의 경우, queenArray에 이미 0값이 있으므로 안됨
queenArray[3] = 1의 경우, 현재 0~3까지 1인 값도 없고 대각선 좌표에 해당하지 않으므로

return true가 된다. row+1하여 n_queen을 수행한다.

3-6. queenArray[4] = 0은 (이제 왜 안되는지 알겠다.)
queenArray[4] = 1도, 2도 이미 해당 값이 queenArray안에 있으므로 안된다.
queenArray[4] = 3의 경우, 현재 0~4까지 3인 값도 없고 대각선 좌표에 해당하지 않으므로

return true가 된다. row+1하여 n_queen을 수행한다.

3-7. queenArray[5] = 0, 1, 2, 3, 4는 모두 이미 있는 값들이라 안된다.
queenArray[5] = 5는 (0,0)과 대각선에 위치해서 안된다.
queenArray[5] = 6은 (1,2)와 대각선에 위치해서 안된다.
queenArray[5] = 7은 (2,4)와 대각선에 위치해서 안된다.
헉! 들어갈 숫자가 없다! => queenArray[4]의 상태로 돌아온다.

queenArray[4]에 3을 넣었을 때까지로 돌아왔으니 다음 수 4를 넣어 보는 것이다.
그런데 이미 queenArray[2] = 4이니 4는 들어갈 수 없다.
queenArray[4] = 5는 (1,2)와 대각선이라서 안되고, 6은 (2,4)와 대각선이라서 안되기 때문에
queenArray[4] = 7이 들어간다. 현재 0~4까지 7인 값도 없고, 대각선 좌표에도 해당하지 않기 때문이다.

return true가 된다. row+1을 하여 n_queen을 수행한다.

3-8. queenArray[5] = 0~7까지 넣어본다. 하지만 결국 맞는 수는 없고...
다시 queenArray[4] = 7로 돌아오지만 맞는 수가 없었으니...
queenArray[3] = 1로 돌아가 (1 다음 수인) 2부터 7까지 넣어 맞는 수를 찾는다.
이런 식으로 계속 수의 유망성을 검사하며 queenArray를 채우면

ex. queenArray[0] = 0일 때

queenArray[0] = 1 일 때

...
이런식으로 queenArray[0] = 7일 때까지의 가능한 배열들을 구해나간다.
※ 참고로 위의 예시 입력값으로 가능할 수 있는 queenArray의 결과값은 아래와 같이 나왔다.

['04752613', '05726314', '06357142', '06471352', '13572064',
  '14602753', '14630752', '15063724', '15720364', '16257403',
  '16470352', '17502463', '20647135', '24170635', '24175360',
  '24603175', '24730615', '25147063', '25160374', '25164073',
  '25307461', '25317460', '25703641', '25704613', '25713064',
  '26174035', '26175304', '27360514', '30471625', '30475261',
  '31475026', '31625704', '31625740', '31640752', '31746025',
  '31750246', '35041726', '35716024', '35720641', '36074152',
  '36271405', '36415027', '36420571', '37025164', '37046152',
  '37420615', '40357162', '40731625', '40752613', '41357206',
  '41362750', '41506372', '41703625', '42057136', '42061753',
  '42736051', '46027531', '46031752', '46137025', '46152037',
  '46152073', '46302751', '47302516', '47306152', '50417263',
  '51602473', '51603742', '52064713', '52073164', '52074136',
  '52460317', '52470316', '52613704', '52617403', '52630714',
  '53047162', '53174602', '53602417', '53607142', '57130642',
  '60275314', '61307425', '61520374', '62057413', '62714053',
  '63147025', '63175024', '64205713', '71306425', '71420635',
  '72051463', '73025164']

4. 이렇게 만들어진 배열을 빈 배열 count에 push 한다.

나는 (내가 보기 좋으라고 ㅋㅋㅋ) 원소들을 모두 붙인 문자열로 만들어 count에 넣었다.

5. 가능할 수 있는 모든 queenArray들이 담긴 count의 길이를 출력한다.

백트래킹의 기본 문제라고 한다.
백트래킹 열심히 공부해야 겠다 ㅜㅜ