TIL #10 N-Queens 알고리즘 (Review)

Joshua Song / 송성현·2019년 11월 29일
1

이머시브_16

목록 보기
11/29
post-custom-banner

알고리즘 스프린트이고 지금까지? 3주밖에 안됐지만 가장 어렵다고 생각하는 N-Queens 스프린트를 정리한다.

Algorithm

알고리즘을 공부하고 연마하는 방법에는 다음과 같은 방법을 사용할 수 있다.

  • 온라인 문제풀이 사이트
  • 유투브
  • 알고리즘 책
  • 구글

What is algorithm:

  • 주어진 문제를 해결하기 위한 일련의 절차들을 정의한 것
  • Computer is dumb, so we need to give specific instructions in code!

내 생각에 알고리즘은 문제를 어떻게 풀지 고민하는 그런 과정인 것 같다. 접근 법이라고 하면 더 명쾌하려나

Backbone.js

이번 스프린트는 jest가 아닌, backbone.js 라는 프레임워크를 통해 테스트를 실행해보고 또 있는 model을 extend해 사용해보는 기회를 가졌다. 아직 자세하게 사용한게 아니고 그냥 채워야 하는 함수 내부의 빈 부분을 작성한 거라 자세히 백본이 엄청 좋다! 이런건 아직 잘 모르겠다. 나중에 프로젝트를 할 때 몇 개의 프레임워크를 찾아보고 비교해보면 더 자세히 알 수 있을 것 같다. 프레임워크는 개발을 할 때 MVC 패턴 적용을 가능하게 해주는, M(model, 데이터), V(view, UI), C(controller, 로직, 데이터 처리)로 코드의 역할을 나눠서 작성하고 프로그램의 구조를 체계화 할 수 있게 해주는 것이다.

N-Queens?

N- Queens 퍼즐? 문제는 N*N 사이즈의 체스판 위에 N 개의 퀸을 놓았을 때 서로 공격하지 못하게 하는 케이스를 구하는 문제이다. 퀸은 상하좌우대각선까지 모든 게 가능한 체스에서 가장 강력한 말이다. 코드스테이츠는 이번 스프린트를 통해 몇가지를 구현하라고 요구했다. 특이한 점은 퀸도 하고 룩이라는, 상하좌우 이동이 가능한 말을 사용해서도 퍼즐을 구현하라는 것이었다. (N-Queens & N-Rooks)

BoardViewer

이번 스프린트에서는 BoardViewer.html라는 visualizer가 제공됐다. 그래서 실시간으로 코드를 작성하고 변화를 주었을 때 객체의 형식으로만 보았다면 상상하기 힘든 체스판을 실제로 볼 수 있어서 도움이 됐다. 그리고 보일러플레이트 코드 (계속 반복적으로 사용하는)를 사용해서 사실 한가지 함수를 구현하는 방법을 깨우치면, 나머지는 일사천리였다.

Board.js

  1. hasRowConflictAt()
    • 특정 행에 겹치는 말이 있는지 확인하는 함수
  2. hasAnyRowConflicts()
    • 체스판 내 모든 행에서 겹치는 말이 있는지 확인하는 함수
  3. hasColConflictAt()
    • 특정 열에 겹치는 말이 있는지 확인하는 함수
  4. hasAnyColConflicts()
    • 체스판 내 모든 열에서 겹치는 말이 있는지 확인하는 함수
  5. hasMajorDiagonalConflictAt()
    • 특정 위치가 주어졌을 때 좌측 위로 올라가다보면 왼쪽상단에서 우측하단쪽으로 내려오는 대각선의 머리가 나오는데, 그 머리가 포함된 대각선의 말이 겹치는지 확인하는 함수
  6. hasAnyMajorDiagonalConflicts()
    • 체스판 내의 모든 대각선을 좌측상단에서 우측 하단으로 내려오는 방향으로 검사했을 때 겹치는 말이 있는지 확인하는 함수
  7. hasMinorDiagonalConflictAt()
      • 특정 위치가 주어졌을 때 우측 위로 올라가다보면 오른쪽상단에서 좌측하단쪽으로 내려오는 대각선의 머리가 나오는데, 그 머리가 포함된 대각선의 말이 겹치는지 확인하는 함수
  8. hasAnyMinorDiagonalConflicts()
  • 체스판 내의 모든 대각선을 우측상단에서 좌측 하단으로 내려오는 방향으로 검사했을 때 겹치는 말이 있는지 확인하는 함수

n-queens conflicts.png

solvers.js

  1. findNRooksSolution()
    • N x N 사이즈의 체스판에서 N개의 룩을 놓을 수 있는 케이스 하나를 반환하는 함수
  2. countNRooksSolutions()
    • N x N 사이즈의 체스판에서 N개의 룩을 놓을 수 있는 모든 케이스 개수를 반환하는 함수
  3. findNQueensSolution()
    • N x N 사이즈의 체스판에서 N개의 퀸을 놓을 수 있는 케이스 하나를 반환하는 함수
  4. countNQueensSolution()
    • N x N 사이즈의 체스판에서 N개의 룩을 놓을 수 있는 모든 케이스 개수를 반환하는 함수

Conflict?

체스판 위에 말이 있는지 없는지는 N의 길이를 가진 배열을 N 개의 키의 값으로 가지고 있는 객체에서 배열 속 값이 1이면 말이 있는 것이고 0이면 말이 없다는 의미이다.

0: [0, 0, 0, 0]
1: [0, 0, 0, 0]
2: [0, 0, 0, 0]
3: [0, 0, 0, 0]

위에 보이는 식의 매트릭스가 4 x 4 형식이다. 현재는 체스판이 비었다는 것이고 0을 1로 만들면 체스 말이 생기는 것이다.

Solution Approach

board.js
먼저 board.js 에 있는 함수들은 문제를 풀 때 사용하는 Board 라는 클래스에 들어가는 함수이다. 그 안에 들어있는 method를 구현하는 함수는 생각보다 복잡하지 않다. For loop을 돌려서 1이 있는지 없는지 확인하면 된다. 나와 내 페어가 사용했던 방법은 reduce로 배열을 다 더하는 것이었는데, 어차피 1 아니면 0이라 다 더했을 때 1이 나오면 말이 하나, 그 이상이면 말이 한개보다 더 많다는 것을 의미해서 생각보다 할만 했다. 대각선 일때는, 좌측에서 오른쪽으로 내려올 때는 행과 열의 index 값이 하나씩 늘어나고, 우측에서 왼쪽으로 내려올때는 행은 하나씩 줄고 열은 index의 값이 하나 늘어났다. 사실 가장 어려웠던 부분은 MajorDiagonal과 MinorDiagonal의
의미었는데 빨리 코드 구현하는 단계로 넘어가려 보니 기본적으로 주어진 코드를 제대로 꼼꼼히 살펴보지 않아서 생긴 일 같다. 그래도 이 board.js에 있는 함수들은 무난하게 잘 했다. for Loop을 잘 사용했다.

solver.js
솔버 함수는 푸는데 정말 시간이 많이 걸렸고 잘하시는 분의 도움을 받아서 완성할 수 있었다. 재귀 함수를 사용해야 하는 것도 알았고 backtracking이라는 개념을 적용해서, 트리처럼 내려가서 풀어야 하는 것도 알았지만 그걸 코드로 어떻게 구현하면 좋을 지 감이 잘 잡히지 않았다. 하지만 머리 속에 있는 그림은 열이던 행이던 기본 틀을 하나 잡고 for loop을 돌려 체스판 위의 조합들이 solution으로 가능한지 안가능한지 테스트 하는 것이었다. 퀸즈의 모든 개수를 세는 함수를 보며 다시 한번 복습해본다. 

window.countNQueensSolutions = function(n) {
  
  let solutionCount = 0;
  let board = new Board({ n: n });

  const recur = function (row){
    if (board.hasAnyQueensConflicts()){
      return; 
    }
    if (row === n) {
      solutionCount += 1;
      return;
    }
    for (let i = 0; i < n; i++){
      board.togglePiece(row, i);
      recur(row + 1);
      //!리턴될 경우 토글된거 다시 빼주기
      board.togglePiece(row, i);
    }
  }

  recur(0);
  
  console.log("Number of solutions for " + n + " queens:", solutionCount);
  return solutionCount;
};

일단 solutionCount는 총 개수의 숫자이고 마지막에 리턴해 줄 값이다. board는 Board라는, backbone으로 뼈대를 잡은 주어진 클래스이다. 먼저 board라는, N x N 사이즈의 빈 체스판을 만들어준다. 그 후 인자로 행을 받는 재귀 함수를 만들어 준다.

const recur 의 첫번째 단계는, board.js에 만들어 준 hasAnyQueensConflicts, 상하좌우대각선 상에서 겹치는 말이 있는지 없는지 확인하는 함수이다. 이 단계는 만들어 내는 조합이 solution이 아닐 경우 바로 그 옵션에서 벗어나 다른 옵션으로 백트래킹을 가능케 한다.

두번째 단계, row === n은 행이 n일 경우, 즉 체스판의 마지막 행까지 올 때 거기까지 왔다는 것은 마지막 행까지 오고도 퀸을 각 행에 놓았다는 것이기에 solutionCount를 하나 늘려준다.

이제 순서상 세번째 단계는 for loop인데 여기서 i는 열을 의미한다. togglePiece 는 기본적으로 주어진, 행과 열의 인덱스를 넣으면 그 위치의 0을 1로, 1을 0으로 바꿔주어 말을 놓아주는 함수이다. 0,0부터 시작하니 그 위치에 말을 놓고 열을 하나 올려서 함수를 다시 돌린다. 첫번째 단계에서는 0,0 위치에 밖에 말이 없으니 if 문들을 다 통과하고 for loop으로 진입한다. 이제 i는 다시 0, row는 1이다. togglePiece후 체스판 위의 말의 위치는, (0,0)과 (1,0)이다. 그리고 다시 열을 하나 올려, row는 2인 상태로 재귀가 돌아간다. 이때, 현재 바뀐 체스판을 hasAnyQueensConflicts()를 실행하면 conflict가 있는 true가 나온다. (0,0)과 (1,0)은 같은 열 index를 가지고 있어 solution에 부합하지 않는다. 그러므로 바로 return 돼어서 처음에, i가 0일때 실행됐던 재귀 함수의 흐름이 끊긴다. 그리고 recur 아래 있는 togglePiece를 다시 실행해줘 (1,0)자리에 있는 말을 없애주고 i++이 실행된다. 이제 그러면 (1,0)을 실패해서 재귀가 끊나고 없앴으니 i가 하나 늘어나 (1,1)자리에 togglePiece로 말을 놓아서 다시 재귀를 돌려 그 체스판을 board.hasAnyQueensConflicts()로 테스트한다. 그리고 통과를 못하면 말을 없애준 후 (1,2)자리에 말을 다시 올려놓아 테스트 하는 것이다. 이렇게 계속 진행되다가 행이 1일 때 테스트를 통과하는 열이 나온다면 그제서야 다음 행으로 넘어간다. 그렇게 쭉쭉 가다가 행이 N까지, 즉 마지막 행까지 재귀를 통해서 가면, if문으로 설정해 놓은 row === n 으로 인해 solutionCount가 하나 늘어나고, 우리는 가능한 옵션이 하나 추가되었다는 것을 안다. 체스판에서 모든 행을 돌아가면서 가능한 열을 돌고 모든 조합을 테스트 한다. 대신 조합을 만들 때 두번 째 행에서 conflict가 걸리면 3번째 4번째 행까지 안내려가도 되기에 시간을 절약한다.

마지막에 리턴되는 solutionCount가 이제 가능한 조합의 개수인 것이다.

마무리

이렇게 코드를 보고 누군가의 guidance가 있다면 이해도 잘되고 쉬운데 혼자서 맨땅에 헤딩하기엔 어렵다. 혼자 시간을 충분히 들여서 했어도 재귀를 깔끔하게 했을지는 모르겠다.실력이 더 늘 나의 모습을 기대하겠다!

profile
Joshua Song / 송성현
Grow Joshua, Grow!
이전 포스트

이머시브 2주차 끝! 주말 TIL #9 Inheritance (상속)

다음 포스트

TIL #11 Web Architecture - Intro

post-custom-banner

0개의 댓글