IMMERSIVE #9 - N-Queens

GunW·2019년 8월 4일

CODESTATES N Queens immersive

약 40시간을 투자하고, 성과를 거두지 못한...스프린트. 리뷰합니다.

절망에 빠졌었지만 Immersive는 빠질 시간조차 주어지지 않습니다.

♛ N-queens

먼저 그림으로 살펴보면 아래와 같습니다.

만약 4x4 판에 퀸을 충돌없이 배치한다면 위와 같이 배치할 수 있겠죠?

그런 경우의 수를 구하는 것입니다.

바로 퀸으로 시작하는 건 어려우니, 필요한 메서드와 N-Rooks로 감을 잡고 시작해봅시다!

🏂 Boards.js

필요한 메서드를 구현하는 파일입니다. 차례차례 확인해보겠습니다 :)

hasRowConflictAt

// 1. rowIndex를 받아서 그 줄의 가로 충돌을 확인합니다.
hasRowConflictAt: function(rowIndex) {
  // 2. 해당 index의 row을 가져옵니다.
  const row = this.get(rowIndex);
  let count = 0;
  // 3. row 내부를 돌면서 1의 개수를 count합니다.
  for (let i = 0; i < row.length; i++) {
    count += row[i];
  }
  // 4. 1의 개수가 1개보다 많다면 충돌입니다.
  return count > 1;
}

hasAnyRowConflicts

// 1. 가로의 모든 충돌을 확인합니다.
hasAnyRowConflicts: function() {
  // 2. 유사배열의 n속성으로 row의 개수를 구합니다.
  const size = this.get("n");
  // 3. 각 row를 돌면서 충돌 여부를 검사합니다.
  for (let i = 0; i < size; i++) {
    if (this.hasRowConflictAt(i)) {
      return true;
    }
  }
  return false;
}

hasColConflictAt

row와 col의 개수가 동일한 점을 활용하는 것이 핵심입니다.

// 1. col의 충돌을 검사하는 메서드입니다.
hasColConflictAt: function(colIndex) {
  // 2. row의 개수와 col의 개수가 동일하므로 row의 개수를 가져옵니다.
  const size = this.get("n");
  let count = 0;
  // 2. 각 row를 돌면서 해당 colIndex의 충돌을 검사합니다.
  for (let i = 0; i < size; i++) {
    const row = this.get(i);
    count += row[colIndex];
  }
  return count > 1;
}

hasAnyColConflicts

hasAnyRowConflicts와 거의 동일합니다.

// 1. 모든 col의 충돌을 검사합니다.
hasAnyColConflicts: function() {
  const size = this.get("n");
  for (var i = 0; i < size; i++) {
    if (this.hasColConflictAt(i)) {
      return true;
    }
  }
  return false;
}

hasMajorDiagonalConflictAt

// 1. \ 모양의 대각선을 검사합니다.
hasMajorDiagonalConflictAt: function(majorDiagonalColumnIndexAtFirstRow) {
  const size = this.get("n");
  let count = 0;
  let rowIdx = 0;
  let colIdx = majorDiagonalColumnIndexAtFirstRow;
  // 2. rowIndex와 colIndex를 1씩 증가시키면 아래 순회는 대각선으로 움직입니다.
  for (; rowIdx < size && colIdx < size; rowIdx++, colIdx++) {
    if (colIdx >= 0) {
      const row = this.get(rowIdx);
      // 3. 대각선 검사에서 1을 발견하면 count합니다.
      count += row[colIdx];
    }
  }
  return count > 1;
}

hasAnyMajorDiagonalConflicts

// 1. 모든 \ 대각선을 검사합니다.
hasAnyMajorDiagonalConflicts: function() {
  const size = this.get("n");
  // 2. 왼쪽 바깥에서부터 오른쪽으로 검사합니다.
  //    4 x 4 라면 -3인덱스부터 검사하는 것이죠. 대각선이니까요
  for (let i = 1 - size; i < size; i++) {
    if (this.hasMajorDiagonalConflictAt(i)) {
      return true;
    }
  }
  return false;
}

hasMinorDiagonalConflictAt

// 1. / 대각선을 검사합니다.
hasMinorDiagonalConflictAt: function(minorDiagonalColumnIndexAtFirstRow) {
  const size = this.get("n");
  let count = 0;
  let rowIdx = 0;
  let colIdx = minorDiagonalColumnIndexAtFirstRow;
  // 2. / 모양으로 검사하기 위해서 감소하면서 순회합니다.
  for (; rowIdx < size && colIdx >= 0; rowIdx++, colIdx--) {
    if (colIdx < size) {
      const row = this.get(rowIdx);
      count += row[colIdx];
    }
  }
  return count > 1;
}

hasAnyMinorDiagonalConflicts

// 1. / 모양의 모든 대각선을 검사합니다.
hasAnyMinorDiagonalConflicts: function() {
  const size = this.get("n");
  // 2. 오른쪽 바깥부터 왼쪽으로 검사합니다.
  for (let i = size * 2 - 1; i >= 0; i--) {
    if (this.hasMinorDiagonalConflictAt(i)) {
      return true;
    }
  }
  return false;
}