[SWEA] 2806 N-Queen-java

문제

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다.
퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.
N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까?
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 자연수 N(1 ≤ N ≤ 10)이 주어진다.

출력

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB

SW Expert Academy

풀이

N-Queen은 굉장히 유명한 알고리즘 문제이다. 나 또한 3년 전쯤 풀려고 시도는 했었다... (대학생 2학년 때 ㅎ-ㅎ)

재귀를 잘 모를때라 결국 못풀었던 것 같다. 이 문제도 사실 이번에 다시 보고 문제 이해를 하는데 시간이 좀 걸렸다. 체알못.. (체스도 잘 모르는 나.. 지뢰찾기에 이어서..) 그래서 검색해봤더니 퀸은 직선, 대각선으로 끝까지 움직일 수 있다고 한다. 그래서 N-Queen에서 요구하는 것은 모든 퀸의 직선,대각선에는 다른 퀸이 놓여있지않게 두는 경우의 수를 찾는 것이였다. 아래의 그림과 같이.

그 경우의 수를 구하기 위해서.. dfs방식을 사용했다. 놓을 수 있는데까지 놓아보고 못놓을 때 그 전으로 돌아가서(백트래킹) 다른 곳에 퀸을 놓고.. 이런 방법!

사실 이 문제는 백트래킹 알고리즘을 사용하는 문제로 유명하다. dfs를 사용하며 퀸을 놓을 수 없을 때 이 전 혹은 그보다 더 전단계로 돌아가는 것이 백트래킹이 된다.

먼저, 나는 0번째 행부터 퀸을 놓으면서 내려오는 방식으로 구현하였다. 즉, 위의 그림처럼 n=8이라고하면 0번째 행에 퀸을 놓고 1번째 행에 퀸을 놓고 .... 7번째 행에 퀸을 놓는다.

위의 그림과 같이 놓을 때 (0,3)에 퀸 하나를 놓고 1번째 행으로 내려왔다고 해보자. 그럼 1번째 행에 놓을 수 있는자리는 0,1,5,6,7열이다. (1,0)에 놓고 재귀를 실행해 그 다음 행, 그 다다음 행 ... 이런식으로 놓아본다. 그래서 놓을 수 없는 상황이 오면 재귀가 끝나고 돌아온다. 그때 (1,1)에 놓아보고 재귀 실행 ... 그 다음 (1,5)에 놓고 재귀 실행... 이런 식으로 모든 경우를 다 해봤다.

if (board[j] == i || i == board[j]+(curr - j) || i == board[j]-(curr - j)) { 
	isPossible = false;
	break;
}

위의 코드는 isPossible이 false로 바뀌는 if문인데 이 조건은 아래와 같다.

• board[j] == i  : 위에서 놓은 퀸이 있는 직선이기에 이 열은 다른 퀸을 놓을 수 없다.
• i == board[j]+(curr - j) : 위에서 놓은 퀸의 오른쪽 대각선이 현재 행의 i를 지나가기에 다른 퀸을 놓을 수 없다.
• i == board[j]-(curr - j) : 위에서 놓은 퀸의 왼쪽 대각선이 현재 행의 i를 지나가기에 다른 퀸을 놓을 수 없다.

위의 그림에서 볼 땐 피해야할 직선이 8개이다. 하지만 퀸을 위에서부터 놓으며 내려올 경우, 퀸은 위쪽에만 놓여있으므로 아래로 뻗어오는 3개의 직선이 통과하는 자리만 피해서 퀸을 놓으면 되기때문에 간단해진다.