백준 9663
Backtraking
조합 알고리즘 문제에 대해 가능한 해를 나열.
조건이 만족할 때만 모든 조합의 수를 살펴본다.
모든 경우의 수 생각해서 가보다가 어떠한 후보들은 더 이상 진행할 필요가 없다면 더 이상 계산 할 필요가 없어진다.
DFS 와의 차이
DFS는 완전탐색을 기본으로 모든 노드를 방문하는 것이 목표이다.
백트래킹은 일단 가보고 후보 해가 될 수 없으면 다음 단계로 진행하지 않고 되돌아 나온다. 둘 다 재귀 호출 형태이기 때문에 헷갈리기 쉽다.
DFS와 backtraking 혼용
가지치기를 통해서 얻은 그래프에 대해서 다시 DFS탐색을 하면서 불필요한 탐색을 줄여나간다.
n = int(input())
chess = [0]*n
#chess[i] = j. i행 j열에 퀸을 두겠다.
def check(x):
for i in range(x): #이전 행에 대해
if chess[x] == chess[i] or abs(chess[x]-chess[i])== x-i: #열이 같거나 대각선상이면
return False #0반환
return True
def dfs(x):
global cnt
if x == n: #퀸을 다 놓았다면
cnt += 1 #카운트업
else:
# 0~n-1열까지 퀸을 놓는 방법을 for문을 통해 돌린다
for i in range(n):
chess[x] = i #행에 대해서 열을 돌기
if check(x) == 1: #놓아도 되면
dfs(x+1) #다음행에 퀸 놓기 수행
cnt = 0
dfs(0)
print(cnt)풀이 방법
- 모든 행에 각각 퀸이 들어가야한다.
- 이전 행을 살피며 열과 대각선에 주의하며 놓는다.
백트래킹은 python으로 구현했을 때 시간초과가 나기 쉬워서 pypy로 제출한다.
힘겹게 코드를 이해했던 문제..ㅠㅠ
