37일차 (01-28-2021)

오늘은 솔로 스터디데이! 이때까지 해왔던 스프린트를 쭉 훑어보았다. 특히 NQueen에서 큰 발전이 있었다. 친구의 조언을 통해 많이 최적화 하고 또 몇가지 문제점을 찾았더니 테스트 케이스를 통과하는데 약 20초 가까이 걸렸었는데, 지금은 1초 조금 넘거나 1초 안되게 통과가 되었다. NQueen을 며칠간 고민을 했는지... 나도 이제 지겹다... 그러나 아직 더 줄일수 있는 방법이 있는 걸로 알고 있는데 거기 까진 내 실력으론 무리인듯하다. 그건 레퍼런스를 참고 해야겠다.

굉장히 많은 개선이 있었다. 먼저 메소드에 대한 개선이다. 먼저 설명을 하자면 Queen의 충돌검사 메소드는 행, 열, 대각선, 역대각선 이 네가지의 충돌검사 메소드를 먼저 구현한 후 모두 합하여 최종적으로 Queen 충돌 메소가 나오게 된다. 행, 열 충돌검사 메소드는 처음 만들었을 때 내가 할 수 있는 가장 효율적인 메소드로 만들었고 더이상 진전은 무리였다. 그러나 대각선, 역대각선은 내가 처음 짠 코드가 굉장히 비효율 적으로 돌고 있다는게 느껴졌다.

먼저 대각선 찾는 법에 대해 설명해 보겠다.

그림이 조금 복잡하지만... 예를 들어서 위처럼 4x4 보드가 있다고 하자, 1은 말이 올라가있는 상태 0은 내려가있는 상태이다. 만약에 보드를 확장해 본다고 생각하면 (3,1)의 인덱스에서 첫행까지 대각선을 주욱 그엇을 때 도착하는 열(COL) 인덱스는 4이다. 열 인덱스 4에 도착하는 대각선 상의 보드위 모든 좌표를 보면 (3,1) (2,2) (1,3) 여기서 알 수 있듯이 행 인덱스 + 열 인덱스가 모두 같다.

처음엔 나는 이를 이용해 2중 반복문을 작성하여 1이 있는 지점의 행과 열의 값을 더하여 비교하는 형식으로 대각선 충돌을 검사하였다. 그러나 이 방식은 매우 비효율 적이고 연산이 많이 늘어 난다.

친구에게서 얻은 힌트로 새로운 방식으로 풀어보았다.

간단한 방식이다. 대각선을 그엇을 때 연장되어 질 수 있는 보드판의 가장 큰 열의 값은 행의 길이 + 열의 길이 이다. 위의 4x4 보드판을 기준으로 6이 되는데 보시다시피 0(0,0)과 6(3,3)은 대각선을 갖지 않는다. 결국 우린 첫행의 열 1 ~ 5 까지만 검사하면 된다.

코드로 설명해보겠다.

SlashConflictAt: function (SlashColumnIndexAtFirstRow) {
  let len = this.get('n')
  if (SlashColumnIndexAtFirstRow === 0 || SlashColumnIndexAtFirstRow === (len- 1) * 2) {
     return false;
  }
  let row = 0;
  let col = SlashColumnIndexAtFirstRow;
  let count = 0;
  while (row !== len) {
    if (this._isInBounds(row, col)) { // 좌표가 유효한 좌표인지?
      count += this.get(row)[col];
      if (count >= 2) {
         return true;
      }
    }
     row += 1;
     col -= 1;
   }
    return false; // fixme
   }

(붙여넣기 하다보니 줄 맞춤이 엉망이다.)

간단하게 첫번 째 행의 열 인덱스 부터 시작하여 row + 1 col - 1 해주면서 만약 1이 있다면 count를 해주는 것이고 count가 2가 넘어가면 충돌이 있다는 것이므로 true를 리턴하였다. 이 메소드에 0부터 행열의 합 최대치 까지 인자로 넣어주면 보드 전체를 검사할 수 있다. 이런 방식으로 백 슬래쉬 또한 비슷하게 구현하였고. 그러니 복잡도가 조금은 줄었다.

솔루션을 찾는 메소드는 어떻게 구현하였냐면.

findQueensSolution = function (n) {
  const solution = new Board({n: n}); // fixme
  let makeAsolution = (row) => {
    if (row > n - 1) {
      return true;
    }

    for (let i = 0; i < n; i += 1) {
      solution.togglePiece(row, i);
      if (!solution.hasAnyQueenConflictsOn(row, i)) {
        let result = makeAsolution(row + 1);
        if (result) {
          return true;
        }
      }
      solution.togglePiece(row, i);
    }
  }
  makeAsolution(0);
  return solution.rows();
};

처음의 방식과는 크게 다르지 않지만 몇가지 키워드가 바뀌었다. 원래 .rows()라는 배열을 불러오는 메소드를 많이 썼었는데 이게 연산이 훨씬 늘어 난다는 것을 알게 되었다. 이 메소드를 최대한 줄였고 다른 키워드로 대체하였다. 그리고 충돌 검사를 전체 보드판을 검사하는 것에서 특정 인덱스를 검사하는 것으로 연산을 조금 더 줄였다. 솔루션의 수를 찾는 것도 위와 별로 다르지 않다.

내일은 레퍼런스를 참고하여 부족한 부분을 보충하여야겠다.