자료 구조 · 알고리즘
[자료 구조/알고리즘] 백트래킹 구현
2025. 7. 25.
fun solve(initialState: State): List<Solution> {
// 탐색을 하며 찾은 정답을 저장할 저장소
val solutions = mutableListOf<Solution>()
backtrack(initialState, solutions)
return solutions
}
fun backtrack(
// 현재 상태
currentState: state,
// 탐색을 하며 찾은 정답을 저장할 저장소
solutions: MutableList<Solution>
) {
// 1. 종료 조건 (Base Case)
// 현재 상태가 문제의 해답이라면
if (isSolution(currentState)) {
solutions.add(currentState.toSolution())
return
}
// 2. 재귀 호출 (Recursive Step)
// 현재 상태에서 다음으로 진행 가능한 모든 상태들을 탐색
for (state in getNextStates(currentState)) {
// 상태 확인 (가지치기)
if (isPromising(state)) {
// 상태 변환 (전이)
...
// 탐색 진행
backtrack(state, solutions)
// 백트랙
// 함수 호출 스택에서 이전 상태로 돌아가는 백트랙은 재귀 호출이 끝난 후 자동으로 이루어진다.
// 상태 되돌리기
// 하나의 경로 탐색이 끝난 후에 다른 경로를 탐색할 수 있도록 상태를 이전 상태로 명시적으로 되돌려야 하는 경우 이 곳에서 수행한다.
...
}
}
}
// 현재 상태가 문제의 해답인지 확인
fun isSolution(state: state): Boolean {
// 문제의 종료 조건 판별 로직
...
}
// 현재 상태에서 다음으로 진행 가능한 모든 상태를 조회
fun getNextStates(state: state): List<state> {
// 다음으로 진행할 수 있는 모든 경우의 수를 조회
...
}
// 상태가 적합한지 확인
fun isPromising(state: state): Boolean {
// 제약 조건 만족 검사 로직 구현
...
}
N-퀸 문제
class Solution {
fun nQueens(n: Int): Int {
// 퀸이 위치한 열 번호를 저장할 배열
val board = IntArray(n) { 0 }
val count = 0
backtrack(n, 0, board, count)
return count
}
fun backtrack(
// 다음 상태 탐색을 위한 변수
n: Int,
row: Int,
// 현재 상태
board: IntArray
// 탐색을 하며 찾은 정답을 저장할 저장소
count: Int
) {
// 1. 종료 조건
// 모든 퀸을 성공적으로 배치한 경우
if (row == n) {
count++
return
}
// 2. 재귀 호출
// 현재 행(row)에 퀸을 놓을 수 있는 모든 열(col)을 탐색
for (col in 0 until n) {
// 상태 확인 (가지치기)
// 현재 위치(row, col)에 퀸을 놓을 수 있는지 확인
if (isPromising(row, col, board)) {
// 상태 변환 (전이)
// 퀸을 배치
board[row] = col
// 탐색 진행
// 다음 행으로 이동
backtrack(n, row + 1, board, count)
// 백트랙
// 상태를 덮어쓰는 방식이므로, 상태 되돌리기 과정은 별도로 필요하지 않다.
}
}
}
// 현재 위치(row, col)에 퀸을 놓을 수 있는지 확인
fun isPromising(
row: Int,
col: Int,
board: IntArray
): Boolean {
// 같은 열에 퀸이 있는지, 대각선에 퀸이 있는지 확인
for (i in 0 until row) {
// 같은 열에 퀸이 있는지 (board[i] == col)
// 또는 대각선에 퀸이 있는지 (abs(row - i) == abs(col - board[i]))
if (board[i] == col || (row - i) == Math.abs(col - board[i])) {
return false
}
}
return true
}
}
fun main() {
val solution = Solution()
val n = 4
val result = solution.nQueens(n)
println(result)
}
- 노드: 퀸들의 현재 배치 상태
- 간선: 한 행에서 다음 행으로 퀸을 놓는 것
- 가지치기: 퀸을 놓으려는 위치가 이미 다른 퀸의 공격 범위에 있는 경우 퀸을 배치하지 않는 것
- 루트 노드: 퀸이 놓이지 않은 초기 상태
- 리프 노드: 더 이상 퀸을 놓을 수 없는 최종 상태
- 정답인 경우: 모든 퀸이 놓인 상태
- 정답이 아닌 경우: 더 이상 퀸을 놓을 수 없는 상태
- 경로 탐색: 루트 노드에서 리프 노드까지 이어지는 일련의 퀸 배치 과정
- 백트랙: 퀸을 놓을 수 없는 경우 이전 행으로 되돌아가서 다른 경로를 탐색하는 것
순열 문제
class Solution {
fun permutations(nums: IntArray): List<List<Int>> {
// 탐색을 하며 찾은 정답을 저장할 저장소 (최종 순열 결과를 저장할 리스트)
val results = mutableListOf<List<Int>>()
// 현재 상태 (현재까지 구성한 순열)
val currentPermutation = mutableListOf<Int>()
// 1부터 n까지의 숫자 사용 여부를 저장할 배열
val used = BooleanArray(n + 1) { false }
fun backtrack() {
// 1. 종료 조건
// 현재 순열의 길이가 m과 같을 경우
if (currentPermutation.size == m) {
results.add(ArrayList(currentPermutation))
return
}
// 2. 재귀 호출
// 1부터 n까지의 모든 숫자를 탐색
for (i in nums.indices) {
// 상태 확인 (가지치기)
// 현재 숫자를 사용할 수 있는지 확인
// 이미 사용한 원소는 건너뛴다
if (visited[i]) {
continue
}
// 상태 변환 (전이)
currentPermutation.add(i)
used[i] = true
// 탐색 진행
backtrack(n, m, currentPermutation, used, results)
// 백트랙
// 상태 되돌리기
currentPermutation.removeAt(currentPermutation.size - 1)
used[i] = false
}
}
backtrack()
return results
}
}
fun main() {
val numbers = intArrayOf(1, 2, 3)
val solution = Solution()
val result = solution.permutations(numbers)
result.forEach {
// 각 순열 출력
println(it.joinToString(" "))
}
}
- 노드: 현재까지 선택된 숫자의 부분 순열
- 간선: 다음 숫자를 선택하는 것
- 가지치기: 이미 선택한 숫자를 다시 선택하지 않는 것
- 루트 노드: 아무 숫자도 선택되지 않은 초기 상태
- 리프 노드: 더 이상 숫자를 선택할 수 없는 최종 상태
- 모든 리프 노드가 정답
- 경로 탐색: 루트 노드에서 리프 노드까지 이어지는 일련의 숫자 선택 과정
- 백트랙: 선택했던 숫자를 선택하지 않은 상태로 변경하고 다른 숫자를 선택하여 경로를 탐색하는 것
조합 문제
class Solution {
fun combinations(n: Int, m: Int): List<List<Int>> {
// 탐색을 하며 찾은 정답을 저장할 저장소 (최종 조합 결과를 저장할 리스트)
val results = mutableListOf<List<Int>>()
// 현재 상태 (현재까지 구성한 조합)
val currentCombination = mutableListOf<Int>()
private fun backtrack(start: Int) {
// 1. 종료 조건 (Base Case)
// 현재 조합의 길이가 m과 같을 경우
if (currentCombination.size == m) {
results.add(ArrayList(currentCombination))
return
}
// 2. 재귀 호출 (Recursive Step)
// start부터 n까지의 숫자를 탐색
// 상태 확인 (가지치기)
// 이전에 선택한 원소보다 더 작은 원소는 강제로 건너뛴다
for (i in start..n) {
// 상태 변환 (전이)
currentCombination.add(i)
// 탐색 진행
// 현재 숫자 다음부터 탐색
backtrack(i + 1)
// 백트랙
// 상태 되돌리기
currentCombination.removeAt(currentCombination.size - 1)
}
}
backtrack(1)
return results
}
}
fun main() {
val n = 3 // 1부터 3까지의 자연수
val m = 2 // 2개를 선택
val solution = Solution()
val result = solution.combinations(n, m)
result.forEach {
// 각 조합 출력
println(it.joinToString(" "))
}
}
문자열 조합 문제
class Solution {
fun letterCombinations(digits: String): List<String> {
val lettersArray = arrayListOf("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
val result = mutableListOf<String>()
val initialState = StringBuilder()
if (digits.isEmpty()) {
return emptyList()
}
fun backtrack(
// 다음 상태 탐색을 위한 변수
digits: String,
index: Int,
// 현재 상태
currentState: StringBuilder,
// 탐색을 하며 찾은 정답을 저장할 저장소
result: MutableList<String>
) {
// 1. 종료 조건
// 모든 자릿수에 대해 처리한 경우
if (index == digits.length) {
val terminalState = currentState.toString()
result.add(terminalState)
return
}
val digit = Character.getNumericValue(digits[index])
val letters = lettersArray[digit]
// 2. 재귀 호출
// 해당 자릿수의 모든 문자를 탐색
for (i in letters.indices) {
// 상태 확인 (가지치기)
val letter = letters[i]
currentState.append(letter)
// 탐색 진행
backtrack(digits, index + 1, currentState, result)
// 백트랙
// 상태 되돌리기
currentState.deleteCharAt(currentState.length - 1)
}
}
backtrack(digits, 0, initialState, result)
return result
}
}
fun main() {
val solution = Solution()
val result = solution.letterCombinations("23")
println(result)
}
부분 집합
- 노드: 현재까지 선택된 부분집합
- 간선: 다음 원소를 포함하거나 포함하지 않는 것
- 가지치기: 없음
- 루트 노드: 아무 원소도 선택되지 않은 초기 상태
- 리프 노드: 더 이상 숫자를 선택할 수 없는 최종 상태
- 모든 리프 노드가 정답
- 경로 탐색: 루트 노드에서 리프 노드까지 이어지는 일련의 원소 선택 과정
- 백트랙: 포함한 원소를 제외하고 다른 경로를 탐색하는 것