TIL_20.05.14(목) - N-Queens

으아... 또 다음날이 돼버렸어...

N-Queens

오늘은 직접 N-Queens를 구현하는 시간을 가지게 되었다.
재귀함수를 정말 직!접!적!으로 사용하기 때문에 진짜... 너무 어려운 스프린트 였지만 역시 재귀를 이해하는데 너무 큰 도움이 된 스프린트였다.

우선,

let recursion = function(row) {
    if(row === n) {
      solution = boardRows;
      return ;
    }
    for(let i = 0; i < boardRows.length; i++) {
      board.togglePiece(row, i);
      if(!board.hasAnyQueensConflicts()) {
        recursion(row + 1); //recursion들이 대기하는 곳
      }
      else{
        board.togglePiece(row, i);
          }
    }
  }
  recursion(0)

아래의 코드는 N-Queens를 구현하는데 처음 사용한 재귀 코드이다. 아니... N-roooks는 됐는데...? 왜 안될까 고민을 정말 많이 했는데 정답은 재귀의 대기에 있었다.

N - Queens는 가로 세로 대각선을 공격 할 수 있기 때문에 충돌이 일어나지 않는 곳에 n개의 Queen을 놓을 수 있는 해답 한개를 return 하는 문제이다.

row에 4이 들어가 4 * 4의 체스판이 생긴다고 가정하면,
우선 row는 0 이기 때문에 for 문으로 인해 (0,0)으로 들어가고 어찌 저찌 해서 row가 1일때 까지 잘 안착했다고 치자. 그런데 row가 2일 때(recursion(2)일 때) 어떤 인덱스(i)에 들어가도 충돌이 일어나게 된다. 그럼 모든 for문을 돌아서 토글을 넣다 뺏다 하게 되는 것이다. 그럼 for문이 종료되고 대기하고 있던 recursion(1)이 실행된다. 이미 recursion(1)은 if문 안에 존재하기 때문에 else문을 실행하지 않고(토글을 삭제하지 않고) 그 행의 다음 인덱스부터 탐색을 시작한다. 그 말은 즉 온전히 백트랙킹을 실행하지 못하고 있다는 뜻이다.

그럼 이렇게는 어때?

let recursion = function(row) {
    if(row === n) {
      solution = boardRows;
      return ;
    }
    for(let i = 0; i < boardRows.length; i++) {
      board.togglePiece(row, i);
      if(!board.hasAnyQueensConflicts()) {
        recursion(row + 1); //recursion들이 대기하는 곳
      }
        board.togglePiece(row, i);
    }
  }
  recursion(0)

문제는 계속 발생한다.

토글을 빼는 과정이 이번에는 else문 안에 들어있지 않기 때문에 이번에는 백트래킹이 이뤄진다. 그리고 탐색을 진행해서 퀸을 성립시키는 토글이 세워져서 solution에 탐색된 배열을 할당했다. recursion(4)는 대기하고 있던 recursion(3)이 실행되고 자신의 토글을 삭제한다. 그리고 다음노드를 탐색하는데 충돌이 일어난다. 이런식으로 recursion(0)까지 올라가게 되는데 , recursion(0)도 자기 자신을 삭제하고 다음 인덱스부터 탐색을 시작한다. 다음 인덱스는 다음 인덱스가 비어있으니 토글을 또 추가할 수 있다. 이 과정을 반복하면서 solution에는 해답 한 개가 반환되겠지만 이는 모든 경우를 다 탐색하는 것 과 같고 해답 한 개만 반환하는 문제에서는 필요가 없다. 그럼 어떻게 추가 조건을 넣어줘야할까?

let recursion = function(row) {
    if(row === n) {
      solution = boardRows;
      return ;
    }
    for(let i = 0; i < boardRows.length; i++) {
      board.togglePiece(row, i);
      if(!board.hasAnyQueensConflicts()) {
        recursion(row + 1);
      }
      if(solution !== undefined){
        return ;
      }
      board.togglePiece(row, i);
    }
  }
  recursion(0)

resursion 재귀호출이 있는 if문 바로 아래에 solution이 할당되어있다면, 바로 return 하는 코드를 추가해준다.

결과 -> 테스트 케이스 모두 통과!

대기 대기 대기....를 기억하자!

아니 제출할 때만 해도 정말 힘들었는데 다 공부하고 나니 이렇게 재밌을수가...
이제 이해는 했으니깐...재귀를 어떻게 처음 구현을 시작해야 할 지 공부를 해야 할 것 같다.