[백준 / BOJ] 9663 N-Queen

문제

출처 : www.acmicpc.net/problem/9663

9663번: N-Queen

N*N의 체스판에 N개의 퀸을 서로 공격할수없도록 배치해야한다. 

이때, 퀸을 놓는 경우의 수를 구하는 문제다.

 

풀이

N의 최댓값이 15이다. 

따라서, 최악의경우 15 * 15의 판에 15개의 퀸을 놓는 경우이므로, 

15! * 15^3 만큼 반복하게된다. 따라서, 모든경우를 봐줄려하면 시간초과가 나게된다.

 

시간초과를 피하기 위해서 체크배열을 이용해서 해당 위치에 퀸을 놓을수있는지 없는지 봐줘야한다.

 

퀸은 가로 세로로 이동 할수있으니, 모든 퀸을 서로 공격할 수 없도록 놓을려면 이미 퀸이 있는 행,열에는 퀸을 놓을수없다. 를 이용해서 

가로,세로를 나타내는 1차원 배열을 두개 선언해주고 풀었다.

 

예를들어, 퀸을 (1,1)위치에 놓을려고 한다면 행을 나타내는 체크배열과 열을 나타내는 체크배열에 체크가 되어있는지 확인해야한다.

만약

Y_check[1] = 1

X_check[1] = 1

이라면 이미 1로 체크가 되어있으니 놓지못한다.

반면에 

Y_check[1] = 0

X_check[1] = 0

이라면 퀸을 놓을수있으므로, 해당 위치에 퀸을넣고 Y_check 와 X_check를 1로 업데이트해준다.

이런 방식으로 모든 퀸을 넣고, N개의 퀸을 전부 체스판에 넣었다면, 백트래킹방식을 이용해 Y_check 와 X_check를 하나씩 풀고 다음 위치를 찾아주며 풀면된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9663%20N-Queen/main.cpp

devxb/JJUNalgo