백트래킹은 기본적으로 모든 경우의 수를 고려해 해를 찾는 방식 중 하나이다. 완전탐색과 중요한 차이는 탐색과정 중에서 조건에 맞지 않다면 빠꾸하고 다음 후보를 탐색하는 것이다.
백트래킹에서 검색할 후보는 트리형태로 표현한다.
상태 공간 트리
위의 그림에서 알 수 있듯이 기본적으로 DFS를 진행한다.
2> b조건 검사를 했을 때, 조건에 부합하지 않으면 그 하위 c는 조사할 필요도 없이 되돌아가 다른 방향으로 탐색을 진행한다.
b 이하의 노드는 탐색할 필요가 없으니 하지 않는 것이다.
용어
- Promising : 해당 노드가 유망한지 검사
- Pruning : 조건에 맞지 않으면 포기하고 루트로 돌아옴
구조
코드 구조는 아래처럼 작성하게 된다
def backtrack(path, options):
# path : 지금까지 선택한 값들의 목록 (부분해)
# options : 이번 단계에서 선택할 수 있는 후보목록 (숫자 목록, 위치 목록 등)
if 조건_만족(path): # 우리가 원하는 조건을 충족하는지 확인하는 부분
정답_처리(path)
return
for 선택 in options: # 현재 단계에서 가능한 모든 선택 하나씩 시도하는 반복문
if 유효하지_않다면(선택): # 유효서을 따지는 부분 pruning
continue
path.append(선택) # 결정
backtrack(path, options) # 다음 단계로 진행(재귀호출을 활용한 dfs)
path.pop() # 백트래킹 (결정 취소)
예를 들어 1~3으로 만들 수 있는 길이가 2인 순열을 만들어보자.
def backtrack(path):
if len(path) == 2:
print(path)
return
for i in [1, 2, 3]:
if i in path: # 중복 방지
continue
path.append(i)
backtrack(path)
path.pop()
backtrack([])
순열은 서로 다른 두개의 수를 뽑는 것이기 때문에 중복되는 경우는 pruning 되는 조건임을 알 수 있다.
또한 지금까지 선택한 값들이 총 2개가 된다면 목표 길이에 도달했기 때문에 재귀함수를 종료할 수 있다. path=[1,2]라면 2가 append 되면서 호출된 backtrack 함수는 바로 path를 print하고 return하기 때문에 3개 이상의 값이 path에 들어갈 일이 없게된다.
출력결과는 아래와 같아진다.
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]
N-Queen 9663
풀이
- Queen의 기동력
먼저 Queen은 위와 같이 체스판에서 이동이 가능하다. 위 아래로 이동하는 것이 가능하고 양옆으로 이동하는 것이 가능하기 때문에 절대로 Queen은 한 열이나 한 행에 두개 이상 존재할 수 없다.
- 작은 N값으로 직접 해보기
N을 4로 잡고 실제로 Queen을 두며 다음 Queen이 올 수 없는 위치를 체크하며 경우의 수를 확인해보자. 2차원 배열에서 행을 하나씩 이동하며 가능한 위치에 Queen을 두는 것으로 진행해보자. 즉 모든 행마다 빈 공간이 한개씩 있어야한다.
처음으로, (0,0)에 Queen을 두게 되면 사진 속 파란색 칸에는 Queen을 둘 수 없게 된다.
2번째 행에서 두가지 빈공간 ((1,2)와(1,3)) 중에 (1,2)를 선택해서 Queen을 둬보자, 다음 3번째 행에 더이상 Queen을 둘 공간이 없어지게 된다. 즉, 이하는 탐색할 가치도 없어진다. 바로 버린다.
2번째 행에서 이번엔 (1,3)을 골라보자. 럭키하게 3번재 행에 한개의 색칠되지 않은 칸이 생긴다.
3번째 행에서 어차피 한개밖에 경우가 없기 때문에 고르게 되면 마지막 행에서 결국 모든 칸이 다 칠해져 Queen을 둘 수 없게 된다.
여기까지가, 바로 첫번째 Queen을 (0,0)에 두는 경우에 대해서 가능한지 경우의 수를 count해본 것이다. (0,0)에 Queen을 두게 되면 어떤 경우에도 4개의 Queen을 서로 공격하지 않게 둘 수 없다.
- 실제 해본 것을 통한 조건 정립하기
N이 4일때 실제 해본 경우를 토대로 조건을 세워보자
a. 같은 행에 위치하면 안됨
같은 행에 Queen을 두지 않기 위해 무조건 DFS로 탐색할때 for문에 1행씩 증가된 값에서 탐색하게 끔 하자
b. 같은 열에 위치하면 안됨
이전에 배치한 Queen들의 열과 같은 열이면 바로 가지치기로 해당 경우를 배제할 수 있다.
c. 대각선에 위치하면 안됨
같은 행에 Queen을 안 두기 위해서 1행씩 증가한 행에서 탐색을 하기 때문에 위쪽 대각선에 위치한 Q는 이미 둘 수 없는 경우로 Flag가 세워졌을 것이기에 밑에 쪽에 있는 대각선인 칸 행- Queen 행은 절댓값을 사용하지 않아도 된다.
- 구현하기
a와b에 대한 조건을 동시에 만족하기 위해서, Queen의 위치를 담고 있는 row를 사용한다.
row=[0]*n
# 각 idx는 체스판에서의 행의 위치
# idx의 element는 체스판에서의 열의 위치 ex. [1]=2 면 (1,2)에 있다는 뜻is_promising함수를 선언해 Queen을 둘 수 있는 곳인지 아닌지 check하여 backtracking을 진행한다.
def is_promising(row_idx):
for i in range(row_idx):
# 이전에 i에 둔 Queen중에 현재 row_idx에 둔 Queen과 column 값이 하나라도
# 겹치는 column이 있으면 안되고,
# 이전에 둔 Queen과 대각선에 위치하면 안된다.
if row[row_idx]==row[i] or abs(row[row_idx]-row[i])==row_idx-i:
return False
return True이전에 둔 Queen의 위치를 모두 row라는 변수에 저장하고 있는데, 이전에 이미 둔 column과 같은 column에 새로운 Queen을 둘 수 없기에 이를 조건문의 첫번째 조건으로,
이전에 둔 Queen과 대각선상에 놓여있는 칸에는 마찬가지로 둘 수 없기 때문에 두번째 조건으로 사용한다.
def n_queens(row_idx):
global ans
if row_idx==n: # 끝까지 갔다는 것은 이상없이 Queen을 빈칸에 둘 수 있었다는 것
ans+=1
return
else:
for i in range(n):
row[row_idx]=i
if is_promising(row_idx):
n_queens(row_idx+1) # promising 하다면 다음 행으로 이동 가능함
마지막으로 같은 행에 둘 수 없다는 조건은 1을 증가시킨 값을 row_idx로 전달해주며 구현한다. 참고로 위의 for문은 column에 대한 반복문이다.
