9663번 N Queen(DFS)

#문제링크 : https://www.acmicpc.net/problem/9663

col : 퀸이 놓인 세로열을 판별하기 위한 체크배열 / d1 : 오른쪽 위로 향하는 대각선 체크배열 / d2 : 오른쪽 아래로 향하는 대각선 체크배열 / cnt : 경우의 수

출처 : https://blockdmask.tistory.com/181

※주의사항

1. 행렬에서 오른쪽 위 대각선과 왼쪽 아래 대각선의 요소들의 인덱스는 일정한 특징을 가진다. 오른쪽 위로 올라가는 대각선에 포함되는 요소들의 행(row)과 열(col)의 값을 더한 값은 같은 대각선에 포함되는 요소들이라면 모두 같은 값을 가진다. 오른쪽 아래로 내려가는 대각선에 포함되는 요소들의 행(row)에서 열(col)을 뺀 값은 같은 대각선에 포함되는 요소들이라면 모드 같은 값을 가진다. 그리고 각 대각선별로 값은 유니크하다. (대각선 값 중복X)

2. row 체크 배열을 따로 놓지 않은 이유는 문제를 트래킹해보면 첫번째 행에서 퀸을 놓고 체크할 부분을 조건에 맞춰 체크해준 뒤, 다음 행으로 넘어가서 같은 일을 반복한다. 즉, DFS의 뎁스가 row와 같다. DFS로 진입하는 것 자체로 행렬의 한 row를 탐색하는 것이라고 생각하면 된다.

3. 종료 조건을 row==N으로 할 경우와 row==N+1로 할 경우의 차이가 무엇인지, 생각해보자.

Code