🔎 N-Queen

❓ 문제링크

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

📄 제출 코드

let answer = 0;
function solution(n) {
  for (let i = 1; i <= n; i++) {
    const board = new Array(n + 1).fill(0);
    board[1] = i;
    dfs(board, 1, n);
  }
  return answer;
}
function 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;
}
function dfs(board, row, n) {
  if(n === row) answer++;
  else {
    for(let i = 1; i <= n; i++) {
      board[row+1] = i;
      if(isValid(board, row+1)) dfs(board, row+1, n);
    }
  }
}

이번에 풀어본 문제는 유명한 N-Queen문제다.
하지만 나는 이에 대해 잘 모르기 때문에 일단 문제를 보고, 반복을 통해 구현하다가 막히게 되었다. 그래서 다른사람의 코드를 참고하여 다시 작성해보았다.

먼저 N-Quuen에 대해 알아보자.
가로,세로 길이가 N인 정사각형 체스판에서 N개의 퀸이 서로를 공격할 수 없도록 배치 하고 싶다. 이때, 이 조건에 만족하도록 배치할 수 있는 방법의 수를 return하는 문제이다.
퀸의 공격범위는 가로 세로 대각선이다.

퀸이 첫번째 라인에 위치하게 되면 해당 라인의 가로 세로 전체에는 어떤 퀸도 위치 할 수 없다.
이는 굳이 2차원 배열이 아니라도 1차원으로 표현할 수 있다.
idx가 세로의 몇번째 인지가 되고, 안의 값이 idx줄의 몇번째에 위치한건지를 이용해 1차원으로 표현한다.
[4,2,3,1]이라면
[0][3] / [1][1] / [2][2] / [3][0]

구현을 해보자. N*N의 정사각형이기 때문에 N만큼의 반복을 통해 먼저 한 줄을 만든다.

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

먼저 한 줄을 0으로 초기화 시키고, 첫번째 값에 i를 넣고, dfs를 시작한다.

function dfs(board, row, n) {
  if(n === row) answer++;
  else {
    for(let i = 1; i <= n; i++) {
      board[row+1] = i;
      if(isValid(board, row+1)) dfs(board, row+1, n);
    }
  }
}

if의 n==row는 row값이 n이 됐을 때 모든 체스판을 다 돌아본 경우다. 이때 answer을 증가시킨다.
그외에는 row+1에 똑같이 퀸을 배치하고, 퀸을 배치해도 되는지 검사후 dfs를 다시 돈다.

function 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;
}

우리가 가려는 row와 i의 값이 똑같으면 false를 리턴.
다음 대각선의 경우이다.
대각선의 경우는 열의 차와 행의 차가 동일한 경우 대각선 경로에 있다.
우리는 인덱스를 열, 인덱스 값을 행 으로 사용하고 있다.

// 열의차 == 행의차
Math.abs(i-row) == Math.abs(board[i]-board[row])

대각선인 경우 이해하기

0 0 0 0
0 1 0 0
0 0 0 2
0 0 0 0

1의 경우 [2,2]
1 1 차이 = 1 1
3 3 차이 = 1 1
4 4 차이 = 2 2

2의 경우 [3, 4]
2 3 = 1 1
1 2 = 2 2
4 3 = 1 1
이렇게 차이가 일정하다.
그래서 행의 차이와 열의 차가 일치하면 대각선에 있는 경우이다.
(대각선이 일치하는 설명은 아직 공부중)

📘 참고

https://ko.wikipedia.org/wiki/여덟_퀸_문제
https://velog.io/@longroadhome/프로그래머스-LV.3-최고의-집합-JS-2xs6gra3