가끔 블로그나 다른 사람들 보다보면 얘네들의 경계가

너무 흐려져있다고 보임.

그냥 대충 설명할게



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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


이 문제를 완전탐색으로 풀면 시간복잡도가 어떻게 될까?


O(N^2*2^(N^2)) 정도 되겠지?

2^(N^2)개의 칸에 대해서 퀸이 있을 케이스와

없을 케이스 모든 게임판을 만들어놓고,

N^2으로 게임판을 순회하며 이게 올바른

게임판인지 확인하는거야.



그러면 이렇게 말할 수 있어


- 아니 퀸 N개라면서 왜 그건 고려안함?

- 아니 대각선은 그렇다치고 당연히 이미 둔 칸과 같은 행, 열에는 피해서 설치해야지 그걸 왜 확인안함?

- 행 열만 고려해서 배치해도 2^(N^2)이 N!이 되는데 뭐하냐


내 풀이를 다시 말해줄게.


모든 게임판을 만들어놓고 N^2으로 게임판을 순회하며 이게 "올바른 게임판인지 확인하는거야."


올바른 게임판인지 확인은 하지만 게임판을 만들어놓고 한거야. 그럼 너무 당연한 처리처럼 보이는 퀸개수, 행, 열 고려는 뭘까?


케이스를 만들어가며 저런걸 고려하는 게 백트래킹이야.

여기서 말한 너무 당연한 퀸개수, 행, 열을 고려하는 것 만으로도

너는 백트래킹의 중요한 내용 중 하나인 가지치기를 했다고 볼 수 있지.


저런 당연한 것을 고려함으로써 해당 상태가 답이 될 수 있는지 (promising), 가망이 없는지 (non-promising) 판단하고 잘라내는 거지.


백트래킹에서 또 다른 중요한 내용은 뭘까?

바로 자신의 상위 상태로 올라가는거야.


현재 상태가 유망하든 그렇지 않든,

현재 상태에서의 더 하위 상태로의 탐색이 다 끝나든,

가망이 없어서 현재 상태를 포기했든


결국 모든 상태를 만들기 위해선 본인의 상위 상태로 되돌아가서 탐색을 계속 진행해야해.


그런데 이 본인의 상위 상태로 올라가는 구현을 상당히 쉽게 만들어 주는 친구가 있어.

그게 바로 dfs라는 탐색 방법인거야.


깊이 우선 탐색이라는 특성상 본인 이전의 상태는 반드시 본인을 직 접 호출한 상위 상태이고, 현재 상태의 탐색이 종료된 뒤 스택의 탑 만 빼내주면 바로 상위 상태로 다시 갈 수 있는거지.


암튼 이렇게 대충 정리하고 폰으로 쓴거라 오타가 있을지도 모르지만 감안하고 봐줬으면 좋겠다.


틀린거나 질문 있으면 댓글 달아주고

틀린거라면 ᄌᄉ 댓글에서 정정해줘