[BOJ9663] N-Queen

문제

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

Note

• 백트래킹
  모든 경우를 탐색하되 조건을 만족하는 경우를 제외하는 가지치기를 잘 수행해야 한다.
  백트래킹이라는 개념을 오해하고 있었는데, 아래 잘 정리된 게시글을 보고 제대로 이해할 수 있었다.

• 나쁜 습관
  문제를 빨리 풀려고 성급하게 접근하다 보니 잘못 푸는 경우가 잦다.
  이 문제도 시간초과를 받았는데, 굉장히 비효율적인 방식으로 완전 탐색을 수행했었다.

• 시간 복잡도 계산
  일반적인 구현은 O(N!)의 시간복잡도를 갖는 것 같다. (확인 및 검증 필요)

Reference

• https://medium.com/@jeongdowon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-backtracking-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-13492b18bfa1