[BackJoon] 충격의 N-Queen 문제 feat.9663번(N-Queen)

 + 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!

 + 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!

 + 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~

 + '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.

 9663번 N-Queen 문제를 제 시간(1시간) 에 풀지 못했다...
 나름 유명한 문제고 못하지는 않는다는 생각에 가볍게 도전했다가, 거대한 망치로 크게 뒤통수를 맞은 기분이다.
 접근방식은 맞... 았다고 할 수가 없다. 문제 해결의 원리를 전혀 파악하지 못했으니까...

  제대로된 가지치기도 못하고 그냥 완전 탐색으로 풀려고하니... 그게 되나... 바보야...

  내가 한 실수 중 가장 큰 것은 가지치기 접근을 잘못 한것이다.
 "시간초과"가 났을 때, 문제의 원리에 초점을 두고 어떻게 해야 불필요한 부분을 생략할 수 있는지를 생각해야하는데, 시스템적-if문을 쓰지 말 것, memcpy로 이전 배열을 복사하는게 아니라 대신 이중 for문으로 배열 초기화 하는것-으로 어떻게 해야하는지 보고있으니... 
정말 바보같다...
알고리즘 공부하고 있는거 맞니??? 에휴...

  오늘의 충격을 토대로 다른 문제 풀 때, 더욱 기운내서 머리를 회전시키자!!! 파이팅!!! ...흑흑흑

---

 *** 문제 : https://www.acmicpc.net/problem/9663

[옳은 접근 방식] (정답)
  일반적으로 경우의 수를 구하는 문제는 백트래킹으로 전체탐색을 한다. 그 중 중요한 것이 '가지치기'로 전체탐색을 할 때, 불필요한 부분을 탐색하지 않게 하는 것이다. 따라서, 문제의 원리를 파악해 불필요한 탐색을 줄여 "시간초과"를 면하는게 해당 문제의 본질이라고 할 수 있다.
  체스에서 퀸은 가로, 세로, 대각선 어디든 갈 수 있는 말이다. 그렇기 때문에, N x N 체스판에 N개의 퀸을 놓는 상황이라면, 1행에 1개의 퀸만 둘 수 있다. 퀸이 하나라도 있는 줄에는 다른 퀸을 절대로 놓을 수 없기 때문이다. 
  따라서, 체스판이 2차배열 형태라고 이중for문을 해주는 것이 아니라, 퀸이 놓여있는 행만 탐색해 주면된다.
  이렇게 되면 O(N^2N)의 시간복잡도가 O(N^N)으로 줄어든다. 고로 시간초과는 안남!!!

P.S. 시간 복잡도 구할 때, 백트래킹에서 재귀 함수 불러주는 횟수로 본다면, O(N!)이다. 8,7,6,5...1

---

** 참고사이트 **

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