[알고리즘] 백트래킹(Backtracking)

• 백트래킹(Backtracking)이란?

• 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.

• 백트래킹의 함수 구조는 다음과 같다.

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

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

• 백트래킹의 특징 정리

• 재귀를 사용(자기 자신을 호출함)
• 반복문이 매우 많이 생길 것 같은 문제에 사용함

• 백트래킹 풀이 방법 정리

• if문이 참이 된다면 참이었을때의 실행문을 실행한다.
• if문이 거짓이라면 for문 안에 각각의 경우에 대하여 값을 바꾸고 자기 자신을 다시 호출하는 재귀함수를 사용한다.
• 문제에 따라서 인덱스 처리가 다르다. 이 부분에 주의해야한다.
• 만약 재귀함수를 호출하는데 인덱스 처리를 잘못 해주게 된다면 시간초과(TLE)가 발생하게 된다.

관련 문항 정리

[[백준] 15649번 N과 M (1)]

[[백준] 15650번 N과 M (2)]

[[백준] 15651번 N과 M (3)]

[[백준] 15652번 N과 M (4)]

[[백준] 15654번 N과 M (5)]

[[백준] 15655번 N과 M (6)]

[[백준] 15656번 N과 M (7)]

[[백준] 15657번 N과 M (8)]

[[백준] 15663번 N과 M (9)]

[[백준] 15664번 N과 M (10)]

[[백준] 15665번 N과 M (11)]

[[백준] 15666번 N과 M (12)]

• [[백준] 9663번 N-Queen]

• [[백준] 2580번 스도쿠]

[[백준] 14888번 연산자 끼워넣기]

• [[백준] 14889번 스타트와 링크]