[Python] Algorithm #04: 완전탐색과 백트래킹

이번 글에서는 완전탐색과 백트래킹을 함께 정리합니다.

 

완전탐색은 가능한 경우를 모두 확인하는 방법입니다.

백트래킹은 그 중 의미 없는 경우를 중간에 잘라내며 탐색 효율을 높이는 방식입니다.

 

코딩테스트에서는 둘을 따로 쓰기도 하고, 함께 섞어서 쓰는 경우도 많습니다.

---

1. 완전탐색이란

완전탐색(Brute Force)은 가능한 모든 경우를 빠짐없이 확인하는 방법입니다.

문제를 빠르게 푸는 핵심은 "모든 경우를 직접 만들어볼 수 있는가"를 판단하는 것입니다.

• 경우의 수가 작으면 가장 확실한 방법입니다.
• 조건이 복잡해도 일단 전부 검사하면 정답을 찾을 수 있습니다.
• 대신 경우의 수가 너무 크면 시간 초과가 날 수 있습니다.

예를 들어 숫자 3개를 골라 합을 구하거나, 문자열의 모든 부분집합을 확인하는 문제는 완전탐색으로 접근할 수 있습니다.

nums = [1, 2, 3]

for i in range(len(nums)):
    for j in range(len(nums)):
        if (i != j):
            print(nums[i], nums[j])

 

 

반복문을 여러 번 중첩해서 모든 경우를 보는 방식이 가장 단순한 완전탐색입니다.

---

2. 완전탐색의 대표 방식

완전탐색은 문제에 따라 여러 형태로 나타납니다.

• 반복문 중첩: 작은 범위의 경우를 직접 모두 확인할 때 사용합니다.
• 재귀 호출: 선택과 비선택을 반복해야 할 때 사용합니다.
• 순열/조합/부분집합 생성: 경우의 수를 체계적으로 만들 때 사용합니다.

from itertools import permutations, combinations

nums = [1, 2, 3]

print(list(permutations(nums, 2)))
print(list(combinations(nums, 2)))

• 파이썬에서는 itertools를 활용하면 순열과 조합을 간단하게 만들 수 있습니다.
• 직접 구현하는 것보다 코드가 짧아지기 때문에, 문제에서 허용된다면 적극적으로 사용할 수 있습니다.

---

3. 백트래킹이란

백트래킹(Backtracking)은 탐색 도중 더 볼 필요가 없는 경우를 만나면 그 경로를 중단하고 되돌아가는 기법입니다.

 

즉, "아무거나 다 해보는 완전탐색"에 "불필요한 가지치기"를 더한 방식이라고 볼 수 있습니다.

• 현재 선택이 조건을 위반하면 더 깊게 들어가지 않습니다.
• 가능한 후보만 이어서 탐색합니다.
• 재귀와 함께 자주 사용됩니다.

백트래킹이 필요한 대표 문제는 순열 생성, N과 M 시리즈, N-Queen, 스도쿠 등이 있습니다.

def dfs(nums, path, used):
	# 경우의 수를 모두 모았으면 출력
	if (len(path) == 2):
		print(path)
		return

	# 아직 사용하지 않은 숫자를 선택
	for num in nums:
		if (num in used):
			continue

		# 선택
		path.append(num)
		used.add(num)

		# 다음 선택으로 재귀
		dfs(nums, path, used)

		# 선택 취소 (백트래킹)
		path.pop()
		used.remove(num)

nums = [1, 2, 3]
dfs(nums, [], set())

 

위의 예시처럼 선택한 뒤에는 다시 원상복구하는 과정이 중요합니다.

---

4. 순열과 조합 만들기

백트래킹은 순열과 조합을 직접 만드는 데 자주 쓰입니다.

 

아래 예시는 모두 재귀를 기반으로 백트래킹을 적용한 구현입니다.

각 선택 후 자신을 다시 호출하고, 원상복구하는 방식으로 모든 경우를 탐색합니다.

 

순열은 순서가 중요하고, 조합은 순서가 중요하지 않습니다.

def permutations_backtracking(nums, path, used):
	# 모든 원소를 선택했으면 순열 완성
	if (len(path) == len(nums)):
		print(path)
		return

	# 아직 사용하지 않은 각 원소를 시도
	for num in nums:
		if (used[num]):
			continue

		# 현재 원소 선택
		used[num] = True
		path.append(num)

		# 다음 위치에 올 원소 선택
		permutations_backtracking(nums, path, used)

		# 선택 취소
		path.pop()
		used[num] = False

nums = [1, 2, 3]
used = {1: False, 2: False, 3: False}

permutations_backtracking(nums, [], used)

 

조합은 보통 현재 위치를 기준으로 뒤쪽만 선택하도록 만들면 됩니다.

def combinations_backtracking(nums, start, path):
	# 2개를 선택했으면 조합 완성
	if (len(path) == 2):
		print(path)
		return

	# start 이후의 원소만 선택 (중복 제거)
	for i in range(start, len(nums)):
		path.append(nums[i])
        
		# 현재 위치 다음부터 선택하도록 (순서 고정)
		combinations_backtracking(nums, i + 1, path)
		path.pop()

nums = [1, 2, 3]
combinations_backtracking(nums, 0, [])

---

5. 백트래킹의 핵심: 가지치기

백트래킹에서 가장 중요한 건 가지치기입니다.

 

현재 상태가 이미 조건을 만족할 수 없다고 판단되면, 더 내려가지 않고 바로 종료합니다.

 

예를 들어 합이 목표값을 넘은 경우, 이미 사용한 숫자가 중복된 경우, 규칙을 위반한 경우 등이 있습니다.

def dfs(total, idx, nums, target):
	# 가지치기: 합이 목표를 넘으면 더 볼 필요 없음
	if (total > target):
		return

	# 모든 원소를 확인했으면 합이 목표와 같은지 확인
	if (idx == len(nums)):
		if (total == target):
			print("가능한 경우")
            
		return

	# 현재 원소를 선택하는 경우
	dfs(total + nums[idx], idx + 1, nums, target)
    
	# 현재 원소를 선택하지 않는 경우
	dfs(total, idx + 1, nums, target)

nums = [1, 3, 5]
dfs(0, 0, nums, 6)

 

가지치기를 잘하면 완전탐색보다 훨씬 적은 경우만 확인할 수 있습니다.

---

6. 자주 하는 실수/주의점

• 재귀 호출 후 원상복구를 빼먹으면 다음 탐색 결과가 틀어질 수 있습니다.
• 방문 여부를 관리할 때는 선택과 해제를 짝으로 맞춰야 합니다.
• 중복을 허용하지 않는 문제에서는 같은 경우를 여러 번 세지 않도록 주의해야 합니다.
• 가지치기를 너무 늦게 하면 백트래킹의 의미가 줄어듭니다.
• 경우의 수가 너무 큰 문제는 완전탐색으로는 해결이 어렵습니다.

---

7. 종합 예제

아래는 1부터 4까지의 숫자에서 2개를 골라 합이 5가 되는 경우를 찾는 예제입니다.

 

완전탐색 방식

def find_cases(nums, start, path, target):
	# 2개를 선택했으면 합 확인
	if (len(path) == 2):
		if (sum(path) == target):
			print(path)
            
		return

	# start 이후의 원소만 선택하는 조합
	for i in range(start, len(nums)):
		path.append(nums[i])
		find_cases(nums, i + 1, path, target)
		path.pop()

nums = [1, 2, 3, 4]
find_cases(nums, 0, [], 5)

 

백트래킹 방식

def find_cases_backtracking(nums, start, path, target):
	# 가지치기: 합이 목표를 이미 넘었으면 이후 더할 수 있는 건 양수뿐이므로 의미 없음
	if (sum(path) > target):
		return

	# 2개를 선택했으면 합 확인
	if (len(path) == 2):
		if (sum(path) == target):
			print(path)
            
		return

	# start 이후의 원소만 선택하는 조합
	for i in range(start, len(nums)):
		path.append(nums[i])
		find_cases_backtracking(nums, i + 1, path, target)
		path.pop()

nums = [1, 2, 3, 4]
find_cases_backtracking(nums, 0, [], 5)

 

이 문제는 완전탐색으로 모든 조합을 확인하고, 조건에 맞는 경우만 출력하는 방식입니다.

규모가 커지면 여기에 가지치기를 추가해서 불필요한 탐색을 줄일 수 있습니다.

---

8. 종합 요약

• 완전탐색: 가능한 모든 경우를 확인하는 방법
• 백트래킹: 불필요한 경우를 중간에 잘라내는 완전탐색
• 재귀와 함께 자주 사용됨
• 순열, 조합, 부분집합 문제에 특히 유용함
• 가지치기를 잘하면 탐색 효율을 크게 높일 수 있음