N-Queens 알고리즘 (N x N 체스판에 N개의 퀸 체스말 놓기)
알고리즘 문제 중에서도 유명한 편에 속하는 N-queens 문제에 도달하게 되었다. 주어진 과제는 '어떻게 하면 n개의 여왕 체스말을 n by n 크기 체스판에서 공격 범위 밖에 놓을 수 있을지를 구현하고, 또 각각의 n에 대하여 몇 가지 방법이 가능한지를 구해라'는 것이었다. 처음 과제를 접했을 땐, 마냥 모든 경우의 수를 구할 수 있도록 n제곱번을 하면 되려나 싶었는데, n개의 말에 대한 모든 경우를 구해야하니 실제로는 어마어마한 경우의 수를 보아야만 하는 것이었다. 가상의 체스판은 행렬의 형태로서 이중 배열을 가지게 하여 구상할 수 있었다. 퀸은 가로, 세로, 대각선 모두가 공격범위이기 때문에, n개의 말을 놓으려면 각 행 또는 열 마다 하나의 퀸이 있어야만 한다. 가장 기본적인 크기..
Programming/Algorithm
2019. 6. 9. 17:00
