[알고리즘] N-Queens

이 포스트는 제가 코드스테이츠 이머시브 과정의 sprint 중 하나인 N-Queens 문제를 어떻게 접근해 풀었는지에 대한 기록입니다.

문제 소개

이미지 출처: leetcode

n-Queens는 가로 세로 모두 n인 정사각형 체스판에 n개의 퀸을 서로의 이동범위(공격범위)가 겹치지 않도록 배치하는 모든 경우의 수를 구하는 문제입니다.

접근 방법

처음엔 아주 대략적인 계획을 세웠습니다.

1. 체스판의 첫번째 칸에 퀸을 놓는다.
2. 다음 퀸을 놓을 수 있는 위치가 어딘지 모두 알아낸다.
3. 알아낸 위치 중 첫번째 위치에 퀸을 놓는다.
4. 다시 다음 퀸을 놓을 수 있는 위치를 모두 알아낸다.
5. .. 반복

막상 구현하려니 조건을 더 세분화 할 필요를 느끼게 되고, 완전히 동작하지 않는 알고리즘이라는 것을 알게 되었습니다.

페어와 함께 더 구체적인 알고리즘을 생각해봤습니다.

- 말을 놓는다.
- 충돌이 없는지 확인한다.
- 가능한 위치에 대해 반복한다.
  - 말을 놓는다.
  - 가능한 위치를 다음 줄에서만 모은다.
  - 가능한 위치에 대해 반복한다.
    - 말을 놓는다.
    - 가능한 위치를 다음 줄에서만 모은다.
    - 가능한 위치에 대해 반복한다.
      - 가능한 공간이 없으면, 혹은 놓은 말 갯수가 N개가 되면, 
        - 결과를 어딘가에 저장한다.
        - 가장 최근에 두었던 말을 체스판에서 지운다.
        - 종료한다.

recursive하게 구현할 수 있겠다는 아이디어를 가지고 시작했고, 위 pseudo code에 반영이 되었습니다.
해결하고자 하는 문제를 작은 단위의 task를 반복해 해결할 수 있도록 했습니다.
똑같은 기능을 반복하며, 기능 수행을 중단 할 적절한 조건을 설정하였습니다.

그리고 backtrack 이라는 개념을 알게되어 알고리즘에 적용했습니다.
문제 해결 가능성이 없는 방향으로는 더 진행하지 않고 한단계 뒤로 돌아가 다른 옵션을 선택해 진행하는 기법입니다.

알고리즘

- 말을 놓는다.
- 충돌이 없는지 확인한다.
  - 충돌이 없으면, 진행
  - 충돌이 있으면, 뒤로 돌아간다.
- [for문] 다음 줄의 모든 위치에대해
  - 말을 놓는다.
  - 충돌이 없는지 확인한다.
    - 충돌이 없으면, 
      - 다음 줄이 없으면,
        - 결과를 어딘가에 저장한다.
        - 현재 위치에서 말을 빼고 다음 칸으로 커서를 옮긴다.
      - [for문] 다음 줄의 모든 위치에 대해
        - 말을 놓는다.
        - 충돌이 없는지 확인한다.
          - 충돌이 있으면, 현재위치에서 말을 빼고 다음 칸으로 커서를 옮긴다.
          - 충돌이 없으면,
            - 다음 줄이 없으면,
              - 결과를 어딘가에 저장한다.
              - 현재 위치에서 말을 빼고 다음 칸으로 커서를 옮긴다.

구현을 알고리즘과 분리해 알고리즘만을 생각하되, 가능한 구체적인 pseudo code를 작성해야했습니다.
사고실험을 하듯, 작성한 pseudo code를 따라서 프로그램의 동작을 따라가 보면서 missing link가 없는지 확인하고, 놓치는 case가 없는지 확인하기도 했습니다.
하지만 여전히 구현상의 허점이 있었고, 이것은 전략적인 위치에 몇 개의(많은) console.log를 찍어 예상대로 동작하지 않는 부분을 찾아내고, 해결해 낼 수 있었습니다.

알고리즘에 집중해 pseudo code를 작성하지 않았다면, 훨씬 더 많은 버그를 만나고, 해결하면서 혼란에 빠졌을 것 같습니다.
이 경험이 앞으로의 코딩 생활에 큰 도움이 될 것 같습니다!