백트래킹 문제 유형 및 코드 기본형
백트래킹(Backtracking)은 해결책에 대한 후보를 구축해 나가다가, 해당 후보가 해결책이 될 수 없음을 발견하는 즉시 이를 포기(백트랙)하고, 다른 후보를 찾아 해결책으로의 가능성을 시도하는 알고리즘이다.
주로 결정 트리(decision tree)의 깊이 우선 탐색(DFS)으로 구현되며 퍼즐, 최적화 문제 등에서 자주 사용된다.
백트래킹 문제 유형 예시
- 순열: 주어진 숫자나 문자열의 모든 가능한 순서를 찾는 문제.
- 조합: 주어진 숫자나 문자열 중에서 일부를 선택하여 만들 수 있는 모든 조합을 찾는 문제.
- N-Queens: N×N 체스판 위에 N개의 퀸을 서로 공격할 수 없는 위치에 배치하는 문제.
- 부분 집합: 주어진 집합의 모든 부분 집합을 찾는 문제.
- 수도쿠: 빈 칸에 숫자를 채워 넣어서 각 행, 각 열, 그리고 9개의 3x3 서브그리드가 모두 1부터 9까지의 숫자를 포함하도록 하는 퍼즐 문제.
- 단어 검색: 주어진 단어를 2D 문자 배열에서 찾는 문제.
코드 기본형
def backtrack(경로, 선택지):
# 종료 조건
if 만족하는 조건:
결과에 경로 추가
return
# 선택지 탐색
for 선택 in 선택지:
# 선택 실행
경로에 선택 추가
선택지에서 선택 제거
# 다음 후보 탐색
backtrack(경로, 선택지)
# 선택 되돌리기
경로에서 선택 제거
선택지에 선택 다시 추가
예시 : 순열 구하기
def permute(nums):
def backtrack(path):
if len(path) == len(nums):
result.append(path[:]) # 깊은 복사
return
for n in nums:
if n in path:
continue # 이미 선택된 숫자는 스킵
path.append(n)
backtrack(path)
path.pop() # 백트래킹
result = []
backtrack([])
return result
nums: 숫자 리스트result: 모든 가능한 순열 저장
