[Python] 백트래킹 구현 방법, 관련 문제 모음

백준 백트래킹 문제 모음

• 9663 N-Queen https://www.acmicpc.net/problem/9663
• 15686 치킨배달 https://www.acmicpc.net/problem/15686
• 2580 스도쿠 https://www.acmicpc.net/problem/2580
• 1062 가르침 https://www.acmicpc.net/problem/1062
• 1759 암호 만들기 https://www.acmicpc.net/problem/1759

 

백트래킹 특징

• 재귀를 이용해야 한다.
• 반복문이 가지 뻗듯이 많이 생길 것 같은 문제

 

백트래킹 풀이 방법

• 재귀 함수의 종료 시점 부터 지정한다.
• 대체로 종료 시점 지정 후 for문이 등장한다.
• for문 안에 각각의 경우에 대해 값을 바꿔가며 재귀함수를 호출한다.
• 시간 초과를 막기 위해 모든 for문을 돌지 않고, 특정 경우에만 실행하도록 가지치기를 하기도 한다.

 

백트래킹의 기본 재귀 함수

def backtracking(loc, ...):
	# 종료를 위한 조건문
	if ...:
		return

	# 현재 위치 부터 for문 
	for i in range(loc, ...):
			backtracking(i+1, ...)
	return

 

백트래킹에서 헷갈리는 인덱스

• 문제에 따라서 해줘야하는 인덱스 처리가 다 다르다.
• 시작점이 정해져 있는게 아니라면 backtracking에 넣는 값은 loc로 구한 값이 아니라 i로 구한 값이어야 한다.
• backtracking함수를 재귀 호출할 때, loc는 이미 포함한 값이 아니라 이 다음에서 접근할 값의 시작이다. 따라서 backtracking(i+1, 뒤에 변수는 i를 이용해서 구한 값)

for i in range(loc, C):
     backtracking(i+1, word+arr[i])
    
for i in range(loc, len(chicken)):
      c_distance = []
      c_distance.extend(distance)
      for idx, h in enumerate(home):
          x, y = h
          c_distance[idx] = min(distance[idx], abs(x-chicken[i][0])+abs(y-chicken[i][1]))
      backtracking(i+1, cnt+1, c_distance)