# 완전탐색 (백트래킹)
백트래킹 유형을 가장 잘 보여주는 백준 온라인 저지의 9663번 N-Queen 문제를 함께 살펴봅시다.
{% embed url="" %}
N-Queens 문제의 규칙은 퀸이 놓였을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다는 것이고, 우리는 **4번째 줄까지 퀸을 놓는 경우의 수**를 구하고 싶습니다.
예를 들어 아래와 같이 퀸의 가로에 퀸을 놓을 수 없습니다.
우리가 어떤 과정을 거쳐 판단을 내릴 수 있을지 봅시다.
이를 우리는 그래프 재귀 형태로 이해해볼 수 있는데요,\
(0,0)을 선택할 경우 아래 4가지 경우를 선택할 수 있습니다.
하지만 이 때, 가로/세로/대각선은 가면 안된다는 조건 때문에 (1,0)과 (1,1)은 더 가 볼 필요도 없겠죠?\
이 "📌**더 가볼 필요 없다**"라는 점이 백트래킹에서 중요합니다. 가지치기를 통해 더이상 조건에 맞지 않으면 가지 않는 것이 백트래킹의 큰 특징입니다.
이후 그래프를 더 파악해봅시다.\
(1,2)를 탐색해본 후더이상 갈 수 없다는 것을 알았습니다.
이런 경우 다시 이전으로 돌아와 다른 경우 즉 (1,3)을 탐색하기 시작합니다. 이렇게 📌**조건에 맞지 않으면 이전으로 돌아오는 것**이 백트래킹의 두번째 중요한 특징입니다.
(1,3)->(2,1)로 선택했을 때에도 안 되는 경로임을 알았습니다.
이 때는 이제 어디로 가야 할까요??
...
맞습니다! 바로 (0,1)로 가야 합니다.
다음과정을 전체적으로 확인하면 다음과 같습니다. \
"가지치기", "이전으로 돌아가서 다른 선택지 확인"에 초점을 두고 파악해봅시다!
위 동영상에서도 볼 수 있듯이, 백트래킹은 재귀함수로 구현합니다.
재귀함수의 핵심은 **호출과 반환**입니다.
Windows 창에서 오류로 인해 여러 창들이 계속해서 보여질 때 한 창이 다른 화면을 호출하는 것을 반복하여 다음과 같은 모습을 보인 적이 있나요? 이 때 가장 안쪽에 있는 창부터 반환시켜야 가장 상위에 있는 창까지 차례대로닫을 수 있습니다.
\
재귀함수의 이러한 특성을 이용하여, 아래 코드에서는 어떤 때에 n\_queens() 함수를 다시 호출하는지, 또 어떤 때에 n\_queens() 함수의 결과값을 반환하는지에 주의하여 봅시다.
```python
n = int(input())
ans = 0
row = [0] * n
def is_promising(x):
for i in range(x):
if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
#+나 X 형태의 경우는 갈 수 없다. 가지치기
return False
return True
def n_queens(x):
global ans
if x == n:
ans += 1
return
else:
for i in range(n):
# [x, i]에 퀸을 놓겠다.
row[x] = i
if is_promising(x):
n_queens(x+1)
n_queens(0)
print(ans)
```
위 코드를 간단히 확인해보면 is\_promising함수는 (1,0) (2,0) 등 세로의 경우와 (1,1)과 (2,2)의 대각선 경우를 가지치기하는 코드입니다.
이후 n\_queens는 이미 재귀함수로 짜여져 있어 if문에 적용이 되지 않으면 자동적으로 이전 경우로 돌아가 다른 경우를 탐색함을 알 수 있습니다.
더 풀어볼 문제로는 N과 M 시리즈가 있습니다.
{% embed url="" %}
백트래킹을 이해해보며 추가적인 내용을 익혀봅시다! 위 동영상처럼 그림을 그려보면 이해에 도움이 됩니다.
{% endembed %}
N과 M 시리즈에서 5번 문제를 같이 볼까요?
{% embed url="" %}
백트래킹의 전형적인 로직으로, 아래 코드에서 pop시키는 과정이 arr에서 7을 pop시키는 과정이고, 이후 다시 다음 숫자8을 그 자리에 넣게 됩니다.
```python
def go(arr):
if len(arr) == m:
print(' '.join(map(str,arr)))
return
for i in range(n):
if len(arr)==0 or List[i] not in arr:
arr.append(List[i])
go(arr)
arr.pop()
n, m = map(int,input().split())
List=list(map(int, input().split()))
List.sort()
go([])
```
## 풀어볼 문제
아래 문제들을 보면 알 수 있듯이, N이 10, 15, 20 이하임을 알 수 있습니다.\
만약 N이 10, 15, 20 이하라면 우선적으로 **완전탐색과 백트래킹**을 의심해보는 것이 좋은 접근입니다.
{% embed url="" %}
{% embed url="" %}
{% embed url="" %}
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://koalas-organization.gitbook.io/koala_codingtest_study/search/backtracking.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.