[JavaScript] TWIL&Review : Algorithm(N-Rooks, N-Queens) (20/11.2~11.3)

알고리즘(Algorithm)-[N-Rooks, N-Queens] 스프린트를 진행했다.

알고리즘 문제 중에서도 유명한 N-Queens를 풀어내보는 시간이었다.
전부터, 이 스프린트의 지옥맛을 미리 얘기하신 분들이 많아서, 시작도 전부터 많이 무서웠다.
스프린트를 시작하고 기본 제공되는 파일을 딱 까보니 더 무서웠다(?). 기본적으로 필요한 메서드 함수 만드는데서부터 많이 털리고.. 최종 알고리즘 함수를 짜볼려니 무서움을 넘어선 해탈의 경지에 다달았다.🤯
정말 역대 스프린트 최고의 난이도였다.. TT 리뷰를 시작해본다.

N-Queens는 무엇을 풀어내는 문제인가?

퀸은 체스판의 '퀸'을 지칭한다.
그러니까, n * n의 판에 n개의 서로 공격하지 못하는 퀸을 놓을 수 있는 경우의 수를 찾아내는 것이다.
퀸의 문제와 더불어, 퀸의 순한 맛인 룩(Rook)의 경우의 수도 함께 풀어보았다.
체스 게임을 몰라도 된다. 퀸과 룩의 이동 가능 범위만 알면 된다.

그림에서 보다시피, 룩은 동서남북 4가지 방향으로 이동하고 퀸은 더해서 대각선 4방향을 추가로 이동하능하다. 두 말 모두 이동 칸 개수에는 제한이 없다. 한 turn에 판의 끝에서 끝까지 갈 수 있다.

판(Board)을 만들어내는 클래스부터해서 사용할 수 있는 메서드들은 이미 많이 작성되어있으나, 일부 메서드들은 우리가 직접 만들어야 했다. 거기서부터 도전의 시작이었다. 완성되지 않은 일부 메서드를 만들고, 준비되어있는 메서드들을 이용해 알고리즘 함수를 짜는 것이 최종 과제였다.

기본적으로 return 되는 체스판은 0과 1로 이루어진 2중배열이다.

let board = new Board({n: 4}) // 4 * 4크기의 판을 생성, 말을 놓으면 0은 1이 된다.
[
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
]

최종 4가지 문제

1. n * n의 판에 서로 공격하지 못하는 n개의 '룩'을 놓은 첫 번째 case를 리턴하는 알고리즘 함수를 짤 것.
2. n * n의 판에 서로 공격하지 못하는 n개의 '룩'을 놓을 수 있는 모든 경우의 수의 count를 리턴하는 알고리즘 함수를 짤 것.
3. n * n의 판에 서로 공격하지 못하는 n개의 '퀸'을 놓은 첫 번째 case를 리턴하는 알고리즘 함수를 짤 것.
4. n * n의 판에 서로 공격하지 못하는 n개의 '퀸'을 놓을 수 있는 모든 경우의 수의 count를 리턴하는 알고리즘 함수를 짤 것.

문제 해결에 앞서 미리 만들어 놓아야 할 메서드

• 주어진 행에 충돌하는 말이 있는지 확인하는 hasRowConflictAt(rowIndex)

• 판 위에 행 충돌이 하나라도 있는지 확인하는 hasAnyRowConflicts()

• 주어진 열에 충돌하는 말이 있는지 확인하는 hasColConflictAt(colIndex)

• 판 위에 열 충돌이 하나라도 있는지 확인하는 hasAnyColConflicts()

• 주어진 슬래시 대각선(/)에 충돌하는 말이 있는지 확인하는 hasSlashConflictAt(SlashColumnIndexAtFirstRow) - 퀸 메서드

• 판 위에 슬래시 대각선 충돌이 하나라도 있는지 확인하는 hasAnySlashConflicts() - 퀸 메서드

• 주어진 백슬래시 대각선()에 충돌하는 말이 있는지 확인하는 hasBackSlashConflictAt(BackSlashColumnIndexAtFirstRow) - 퀸 메서드

• 판 위에 백슬래시 대각선 충돌이 하나라도 있는지 확인하는 hasAnyBackSlashConflicts() - 퀸 메서드

1차, 2차 난관.

먼저 메서드 얘기부터 해본다.

일단, 행과 열을 검사하는 메서드까지는 괜찮았다.
행 검사는, 행을 가져오는 이미 작성된 메서드를 이용해서 검사했고,
열 검사는 행을 가져오는 메서드의 고정된 index(판이 이중배열로 표현되니 열이 index라고 할 수 있다)의 요소를 하나씩 검사했다.

1차 난관은 슬래쉬(/)와 백슬래쉬(\) 검사였다.
일단 행이 넘어가면서 index가 +1, -1씩 변화되는 방법을 생각해냈다.
그러나 이 방법으로는 검사를 못하는 사각지대가 생겨난 듯 했다.
(행 0, 열 0부터 시작해 내려가므로, 그림의 사각지대 부분은 판 크기보다 더 크게 열이 넘어가거나, 마이너스(-)열부터 시작했어야했다.)

다행히도, 기존 설계된 Board 클래스의 속성이 판을 벗어난 index까지 접근할 수 있게 설계되어있었다. 그래서 판보다 더 큰 열과 더 적은 마이너스 열에까지 접근이 가능했다.
판의 크기인 n에 대해서 얼마나 열을 벗어나야하는지 규칙을 찾는 것이 2차 난관이었다.
여기서 고민하느라 시간을 많이 썼다.TT 그래도! 페어님과 머리를 싸매 규칙을 찾아 수식으로 표현한 것을 대입해 자력으로 해결할 수 있었다. (휴)

또 다른 방법이 있었다.
민철 엔지니어님의 오피스 아워 시간에 결정적인 힌트로 알려주셨다.
(행과 열의 합이 같다. 리팩토링 해 볼 과제!)

2차까지의 난관을 넘어 한숨 돌리고, 정신을 차렸더니 이제 시작이었다.
본 문제인 알고리즘 함수를 짤 시간이 왔다 ... ^^ ...

3차 난관.

이제 모든 존재하는 메서드를 활용해서 case를 찾아내는 알고리즘을 짜야한다.
..... 머리에 쥐나는 느낌은 정말 오랜만이었다. 의존할 곳은 콘솔창과 test가 뱉어주는 오류메세지 뿐이었다. 이하 생략한다. 최종적으로 완성한 코드를 수도코드로 써본다. 정말 쥐어짜서 만든거라 효율적이거나 아름답지 못하다. 아름다움과 효율은 레퍼런스 코드에서 찾기로 했다.. ㅎ

// n * n의 판에 n개의 서로 공격하지 못하는 n개의 '룩'을 놓은 첫 번째 case를 리턴하는 함수
findNRooksSolution (n) {
  // 1. n * n크기의 체스판 생성
  
  // 2. 행 번호를 인자로 받는 재귀함수 생성
  // 2-1. 행 번호가 n과 같아지면(행의 끝까지 말을 놓고 재귀된 것), !탈출!
  // 2-2. 행에 대해 모든 열(index)을 도는 for loop 생성
  // 2-2-1. 일단 말을 놓음
  // 2-2-2. 놓고 나서, 어느 행과 열에도 충돌하는 말이 없다면, 행+1을 인자로 재귀
  // 2-2-3. 충돌한다면, 말을 회수 (다음 열로 이동)
  
  // 3. 재귀함수 실행(행 0부터)
  // 4. 완성된 체스판을 배열형태로 return(메서드 이용)
};

// n * n의 판에 서로 공격하지 못하는 n개의 '룩'을 놓을 수 있는 모든 경우의 수의 count를 리턴하는 함수
countNRooksSolutions(n) {
  // 1. n * n크기의 체스판 생성
  // 2. 0부터 시작하는 count 생성
  
  // 3. 행 번호를 인자로 받는 재귀함수 생성
  // 3-1. 행 번호가 n과 같다면(행의 끝까지 말을 놓고 재귀된 것), count를 올리고, !탈출!
  // 3-2. 행에 대해 모든 열(index)을 도는 for loop 생성
  // 3-2-1. 일단 말을 놓음
  // 3-2-2. 어느 행, 열에도 충돌하는 말이 없다면, 행+1을 인자로 재귀
  // 3-2-3. 재귀에서 돌아오면, 말을 회수 (다음 열로 이동) --> 모든 case를 확인해야하므로!
  
  // 4. 재귀함수 실행(행 0부터)
  // 5. count를 return
};

// n * n의 판에 n개의 서로 공격하지 못하는 n개의 '퀸'을 놓은 첫 번째 case를 리턴하는 함수
findNQueensSolution(n) {
  // 1. n * n크기의 체스판 생성
  // 2. n이 0, 2, 3이면, 태초의 체스판 return (case 존재 X)
  // 3. n이 1이면, 말 하나 놓고 체스판 return (case 딱 1개 존재)
  // 4. 재귀함수 판단용 아무 값 없는 변수 solution 선언
 
  // 5. 행을 인자로 받는 재귀함수 생성
  // 5-1. 행 번호가 n과 같다면(행의 끝까지 말을 놓고 재귀된 것), solution에 체스판을 할당하고, !탈출!
  // 5-2. 행에 대해 모든 열(index)을 도는 for loop 생성
  // 5-2-1. 일단 말을 놓음
  // 5-2-2. 어느 행, 열, 슬래쉬, 백슬래쉬에도 충돌하는 말이 없다면, 행+1을 인자로 재귀
  // 5-2-3. 재귀에서 돌아온 후, (검사) solution에 case가 할당되어있다면, 그대로 stop
  // 5-2-4. 아니라면, 말을 회수 (다음 열로 이동)
  
  // 6. 재귀함수 실행(행 0부터)
  // 7. 완성된 체스판을 배열형태로 return(메서드 이용)
};

// n * n의 판에 서로 공격하지 못하는 n개의'퀸'을 놓을 수 있는 모든 경우의 수의 count를 리턴하는 함수
countNQueensSolutions(n) {
  // 1. n * n크기의 체스판 생성
  // 2. 0부터 시작하는 count 생성
  
  // 3. 행을 인자로 받는 재귀함수 생성
  // 3-1. 행 번호가 n과 같다면(행의 끝까지 말을 놓고 재귀된 것), count를 올리고, !탈출!
  // 3-2. 행에 대해 모든 열(index)을 도는 for loop 생성
  // 3-2-1. 일단 말을 놓음
  // 3-2-2. 어느 행, 열, 슬래쉬, 백슬래쉬에도 충돌하는 말이 없다면, 행+1을 인자로 재귀
  // 3-2-3. 재귀에서 돌아오면 말을 회수 (다음 열로 이동)
  
  // 4. 재귀함수 실행(행 0부터)
  // 5. count를 return
};

난관을 넘은.. 후기

이렇게 N-Rooks, N-Queens 알고리즘 스프린트의 대장정은 마무리 되었다. (휴)

글을 쓰며 정리하며 흐름을 보니, 흐름까지는 누구나 감이 올 만한 난이도이다.
근데, 진짜 처음엔 어느 타이밍에 말을 놓아야하는지 조차 감이 안와서 마음고생을 많이 했다.

완성 후 제출하고 나서는, 머리에 쥐가나서 다시 쳐다보고 싶지 않아 외면하고 있다가.. 마침 HA시험 후 SoloDay라는 개인 시간이 주어져 기념비적인 고통을 블로깅하며 다시 정리해본다.
힘든 시간이었지만, 이 스프린트를 통해서 항상 어려웠던 개념인 '재귀'에 많이 익숙해졌고, 이제 내 사고로 돌려보는게 꽤 감이 잡히는 느낌이다. 덕분에 HA에서 재귀문제를 해결할 수 있었다.

역시 사람은 크게 당하고 끝까지 사지에 몰리면서 성장하는 법이다.
가장 힘들었던 만큼 가장 성취감 있고, 사고력을 많이 키울 수 있었던 값진 시간이었다.

벌써 이머시브 코스 3주차이고, 이제 스프린트 Part2로 넘어간다.
매주 월, 수, 금 주 3회 운동! 이때까지 한 번도 빠지지않고 잘 해왔다.
블로깅도 스프린트마다 나름 꾸준히 해왔다.
앞으로 서버와 DB파트로 들어가면 난이도가 많이 어려질테지만.. 할 수 있다! 결코 지지 않으리라. 정빈 화이팅!