N-Queens 문제해결하기

페어프로그래밍으로 하는 문제 중 가장 재미있는 시간이었다. 도전적이기도 하고 사실상 답이 정해져있는 다른 방법에 비해 자료구조를 동반하는 알고리즘은 방법에 제한이 없다보니 창의적인 방법을 시도하는 느낌이 드는게 굉장히 즐거웠다. 익숙하지 않은 남이 써놓은 구조체(코드)를 제한된 시간내에 빨리 파악하고 누군가 불친절하게 써놓은 코드를 거꾸로 해석해가는 것도 즐거운 작업이었다.

목표

N-Queens 의 목표는N * N 사이즈의 보드에 rook 와 queen을 놓는 경우의 수와 놓은 모양의 배열을 만드는 것이다. 내가 푼 방식은 비효율적인것 같긴하지만 OOP를 도전적인 문제를 해결하는데 재미있게 사용한 첫 경험을 제공해주었다.

사용한 자료구조

해결 과정

처음엔 절대로 사용하지 않을 자식은 생성하지 않는 구조를 만들다가 보드의 사이즈가 8을 넘기자 메모리 크래시를 경험할 수 있었다. 트리를 리프까지 채우기 위해 만든 메서드가 재귀인 문제의 원인이었다. Look든 Queen 이든 세로(컬럼)은 딱 한개의 말만 존재할 수 있다는 점을 이용해서 문제를 해결했다. 위의 빨간색 X 표시는 사용하지 말아야할 컬럼의 번호를 차일드에게 넘겨주어서 차일드가 재귀함수를 스마트하게 호출하게 한 덕에 만들지 절약한 메모리 공간이라고 볼 수 있다.

리프가 들고 있는 path는 Look의 배치도가 된다. 여기서 리프.path === N사이즈의 보드에서 모든 LOOK 경우의 수라고 보면 된다.

이제 만들어진 리프를 꺼내서 이번 과제가 제시한 목표를 클리어하면 된다. 아무 리프나 꺼내서 배열에 0,1 로 표시를 하면 된다. 이건 자료구조에 비하면 간단하다. 특히나 LODASH에서 제공하는 board Model은 배열에 값을 쉽게 반영하게 해준다. 원래 View, Model 구조를 알려주기 위해서 서비스로 넣은거라 생각했는데 생각보다 더 중요한 구조체였다.

Queens의 경우는 Look보다는 어려웠지만 더 빨리 풀었다. 처음엔 만들어진 path를 수동으로 파싱해서 대각선처리를 하려고 했는데 자신보다 높은 레벨의 대각선을 체크하는 문제에 직면하자 if 문 한 두개로 처리할 규모가 아니게 되었다. 그래서 일단 LOOK의 리프를 2중 배열에 집어넣고 대각선 체크함수를 활용하는 방법으로 우회하게 되었다.

개선할점

• 대각선 등 배열에서 충돌을 체크하는 함수가 약간 하드코딩된 느낌이 있다. 그래봤자 IF 두개 정도에 배열 사이즈에 영향을 전혀 받지 않을만큼 견고했지만, 배열의 성질을 활용하는 흥미로운 방법을 적용하면 더 흥미로운 코드를 만들 수 있을 것같다.
• 사이즈 1부터 사이즈 9까지 queens의 모든 가능성을 체크하는데 까지 1초가 걸렸다. (내 맥북이 13년형 인걸 감안하면 감탄스럽지만) 사실 OOP 대신 Queens나 Look가 보드 속에서 나타내는 성질을 활용하면 훨씬더 빠르게 문제를 처리할 수있다. (여기 OOP를 쓴건 닭잡는데 소잡는 칼을 쓴것같다)