[Swift] 백준 - N-Queen

문제

https://www.acmicpc.net/problem/9663

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

접근 방법

백트레킹 문제. dfs로 접근하되, 필요없어 보이는 노드는 무시하며 탐색(프루닝)

처음엔 2차원 배열로 둘 수 있는 공간 true 둘 수 없으면 false 로 두고 채크하는식으로 풀었는데 시간초과..

불필요한 부분들 줄여가면서 라인 한줄만 체크하면 된다는걸 알게되서 대각선 체크를 굳이 다 하지 말고 depth 한칸당 좌우 shift를 해줌으로써 해결

코드

풀이 1 (시간초과 ㅠ)

풀이 2(통과)