[BJ] 9663 - N-Queen(백트레킹)★

 

상당히 어려웠는데 퀸에 이동을 막는 규칙을 어떻게 정해야하는지 어려웠다.

 

퀸은 이렇게 상하좌우 대각선으로 움직일 수 있다.

 

그리고 0번쨰열에 아무곳에나 퀸을 두면 같은 열에 둘 수 없다.

그러면 열을 재외하고

행,왼쪽대각선,오른쪽대각선 을 체크를 해 주어야한다.

 

1.행

행을 비교하는 0,1과 2,1이 어떻게 같은 행에 있는지 판단하는가?

y값이 같은지 확인하면 된다.

둘다 1

 

2.왼쪽 대각선

 

왼쪽 대각선을 비교하는 1,2과 3,0이 어떻게 같은지 판단하는가?

x + y값이 같은지 확인하면 된다.

둘다 3

 

3.오른쪽 대각선

오른쪽 대각선을 비교하는 1,1과 3,3이 어떻게 같은지 판단하는가?

x - y값이 같은지 확인하면 된다

둘다 0

 

 

주의사항

2차원 배열로 만들면 안되고, O(1)로 판단하여 가지치기를 해야한다 즉 백트레킹으로 풀어야 시간초과가 나지않는다.

 

 

이게 백트레킹 기본문제라니.. 멀고 멀었다 

특히 퀸의 이동제약을 체크하는걸 생각하는게 너무 어렵다.

단순히 2차원 배열로 체크하면 안된다.