9663번

[BOJ] 9663번 : N-Queen (JAVA/자바)

문제 알고리즘 고민 퀸은 가로, 세로, 4방향의 대각선으로 공격이 가능하다. 따라서 퀸을 놓을 수 있는지 확인하려면 놓는 위치에서 위에 해당하는 범위에 다른 퀸이 있는지 확인을 해야한다. 없다면, 놓는 퀸이 다른 퀸을 공격할수도, 다른 퀸이 놓는 퀸을 공격할수도 없을것이다. 처음에는 dfs 통해 N x N 배열을 돌면서 퀸을 한쪽에 놓고 그 위치에서부터 배치가 가능한지 위의 공격범위로 총 8방향을 검사하면서 진행했다. 하지만, N이 8만 되도 시간이 엄청나게 드는것을 확인할 수 있었다. 이후 다른 방법에 대해 생각을 했다. 퀸을 배치할때, 가로나 세로 부분에 한부분은 무조건 차지하기 때문에 사실 배열이 2차원이 아닌 1차원 배열로도 표현을 압축해서 하는 것이 가능하다는 것을 확인했다. 세로 1 2 3 4..