N-queens에 도전하다

 

 

 N-queens는 nxn 사이즈의 체스판이 주어졌을 때 서로를 공격할 수 없는 자리에 n개의 퀸을 배치하는 방법을 구하는 문제다. 한 줄로 이렇게 요약해 두니 간단해 보이지만, 막상 문제풀이에 뛰어드니 금세 정신이 아득해졌다. 고려해야 할 부분이 너무 많았다. 

 

N-queens 문제 풀이를 앞두고 전략을 세울 때 고심했던 첫 번째 부분은 '수많은 경우의 수 가운데, 퀸 간의 충돌이 일어나지 않는 경우를 어떻게 찾을 것인가'였다. 체스판의 사이즈가 4x4 정도밖에 안 된다 하더라도 퀸 4개가 놓일 수 있는 경우는 총 4^4, 즉 256가지나 된다. n이 1씩 증가할 때마다 배치 가능한 경우가 기하급수적으로 증가하는 가운데, 모든 케이스를 하나 하나 체크하고,  것은 정말 무식하도록 비효율적인 일일 것이라 생각했다.

 

그래서 세운 전략이 다음 그림과 같다.

도식화 시킨 것을 보면 알 수 있겠지만 일종의 트리와 같은 형태를 구상했다. 대신 수많은 경우의 수가 끝까지 가지를 쳐 나가게 두지 않고, 충돌이 발생하는 경우에는 가차없이 가지를 잘라 냈다. 이러한 전략을 골자로 하여 코드를 짜 내려가기 시작했다. 

 

또 다른 난관은 '대각선에서의 충돌을 어떻게 찾을 것인가'였다. 행과 열에서 충돌을 찾는 방법은 이차원 어레이의 인덱스만 잘 활용한다면 누구라도 쉽게 고안해 낼 수 있을 것이다. 그러나 대각선의 경우는 이야기가 달라진다. 처음에는 단순 반복문을 통해 행과 열의 인덱스를 더하거나 빼는 식으로 대각선을 검사하려는 시도를 했다. 그러나 그렇게 하다 보니 기준점의 위치가 어디인지에 따라 고려해야할 사항이 너무 많아졌고, 그 전략을 고수하다간 스파게티 코드라는 비극적 결말을 맞을 것 같았다. 게다가 major diagonal, minor diagonal까지 고려를 해야 하니... 머리가 터질 것 같던 와중에 동료들로부터 조언을 받아 답을 얻었다.

 

위의 표는 4x4 체스판의 major diagonal을 기준으로 작성된 것으로, 표의 각 칸에는 행 인덱스에서 열 인덱스를 뺀 값이 들어가 있다. 표를 살펴 보면 금방 눈치챘겠지만 같은 값들이 대각선 형태로 배치되어 있음을 알 수 있다. 다시 말해서 행 인덱스 - 열 인덱스를 했을 때, 값이 같으면 한 대각선 상에 있는 것이다! 이제 한 대각선에 퀸이 1개 이상 있는지만 체크하면, 충돌 여부를 쉽게 검사할 수 있게 되었다.

 

 

 

---

 

 

 

이전에도 알고리즘 문제는 제법 풀어 보았지만, N-queens만큼 전략 구상에 긴 시간을 쏟아본 문제는 없는 것 같다. 다 푸는데 이틀 가량이나 걸렸으니 꽤 오랫동안 골머리를 앓은 셈이다. 심지어 어젯밤에는 꿈 속에서도 맥북을 붙잡고 있었다...

그래도 많은 게 남은 것 같아 기쁘다. 커다란 문제를 작게 쪼개어 차근 차근 해결하는 방법, 알고리즘적 사고에 대한 맛보기, mocha test에 전부 pass가 떴을 때의 뿌듯함까지.... 일종의 러너스 하이 같은 걸 느끼며 n-queens에 임했던 것 같다.