ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Javascript] - N-Queens 구현하기
    Programming/Javascript 2019. 4. 12. 09:53
    • N-Queens란 무엇인가
      - N * N의 크기의 체스판에 퀸을 N개 배치하는 문제이다
      - N개의 퀸은 서로 공격할 수 없다
      - 체스에서 퀸은 자신의 위치에서 상하좌우, 그리고 대각선 방향으로 공격을 할 수 있다

    8*8의 체스판에서 8개의 퀸을 서로 공격하지 않도록 배치하는 예

    - 위의 문제를 구현하기 위해서는 백트렉킹 알고리즘을 사용해야한다

     

      • 백트렉킹이란 무엇인가
        - 특정 노드에서 유망성을 점검하고, 유망하지 않다면 그 노드의 부모 노드로 돌아가서 다른 노드에 대한 검색을 계속하는 절차

        - 백트렉킹 알고리즘은 전수조사 방법중 하나인 깊이우선탐색으로 시작한다 그리고 각 노드에서 유망하지 않은 노드들은 탐색 하지 않고 유망한 노드에 대해서만 탐색을 진행한다 (가지치기, Pruning)

        - 탐색의 순서
         1. 깊이 우선 탐색을 실행
         2. 각 노드의 유망성 검사
         3. 유망하다면 계속 탐색
         4. 유망하지 않다면 부모 노드로 돌아가서 탬색을 진행(백트렉킹)

        - 이 방법을 사용하면 깊이 우선 탐색보다 검색의 수를 줄일 수 있다
      • 코드 구현 중 어려웠던 부분
        - 코드를 구현할 때 경우의 수를 찾는 부분에서 Math.random() 메소드를 사용하였더니 CallStack이 넘치는 현상이 발생하였다

        - 백트렉킹 방식을 사용하지 않고 진행하려니 테스트가 돌아가지않는 오류가 발생하였다

        - 아래의 코드는 Queen을 배치하는 것이 아닌 Rook을 배치하는 경우의 수를 찾아내는 코드이다

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    <-------------------------------------------------------------------------------------->
    window.findNRooksSolution = function (n) {
      var findRooks = new Board({n: n});
      var solution = [];
     
      function recursion(){
        var arr = Array(n).fill(null).map(()=> Array());
     
        for(let i = 0; i < n; i++){
          for(let j = 0; j < n; j++){
              arr[i][j] = 0;
          }
        }
     
        for(let i = 0; i < arr.length; i++){
          arr[i][Math.floor(Math.random() * n)] = 1;
        }
     
        for(let i = 0; i < n; i++){
          findRooks.attributes[i] = arr[i];
        }
     
        if(!findRooks.hasAnyRooksConflicts()){
          solution = arr;
        } else{
          recursion();
        }
      }
     
      recursion();
      
      return solution;
    };
    cs

     

     

    • 시간이 더 주어진다면 구현해보고 싶은 것
      - 위의 코드처럼 Math.random() 메소드를 사용하지 않고 백트렉킹을 사용하여 구현해보는 것
      - Recursion을 사용했을 때 무한루프에 빠지지 않는 방법으로 구현해보는 것
      - 코드의 실행시간을 단축시키는 법을 생각하고 거기에 맞는 솔루션을 찾는 것

     

    이번 도전에서는 나의 한계를 너무나 느꼈다. 검색을 사용하지 않고 나만의 방식으로 해결하려니 한계가 보였다

    좋은 솔루션이란 무엇인가에 대한 생각을 더욱 하게되는 도전이었다.

    시간이 난다면 다시한번 풀어보고 싶은 문제이다.

    'Programming > Javascript' 카테고리의 다른 글

    [Javascript] - N-Queens 구현하기  (0) 2019.04.12
    [Javascript] - 프로토타입(prototype)  (0) 2019.04.08

    댓글 0

Designed by Tistory.