“N×N 의 체스판에 Queen이 서로 공격하지 않도록 놓을 수 있는 방법을 찾아라.”

위 문제는 유명한 N-Queen 문제이다.

자료구조 시간에 N-Queen 문제를 풀면서 백트래킹을 마스터했다고 생각한 LIBe는

보다 더 어려운 문제를 풀이보기 위해서 문제를 다음과 같이 변경하였다.

“체스판에 장애물들이 있고, Queen이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Queen의 개수는 몇 개일까?”

그러나 세상의 모든 일은 생각대로 되지 않는 법. 코딩 스킬이 부족했던 LIBe는 위 문제를 풀다가 포기하고 결국 문제를 다음과 같이 변경하였다.

체스판에 장애물들이 있고, Bishop이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Bishop의 개수를 찾는 프로그램을 작성하시오. (Queen은 가로, 세로, 대각선으로 이동할 수 있으나, Bishop는 대각선으로만 이동이 가능하다.)

Bishop timer 1s memory 64MB

Bishop 1s 64MB