[자료 구조/알고리즘] 백트래킹 구현

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 {
    private var count = 0

    fun nQueens(n: Int): Int {
        // 퀸이 위치한 열 번호를 저장할 배열
        val board = IntArray(n) { 0 }
        backtrack(n, 0, board)
        return count
    }

    fun backtrack(
        // 현재 상태
        n: Int,
        row: Int,
        // 탐색을 하며 찾은 정답을 저장할 저장소
        board: IntArray
    ) {
        // 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)

                // 백트랙

                // 상태를 덮어쓰는 방식이므로, 상태 되돌리기 과정은 별도로 필요하지 않다.
            }
        }
    }

    // 현재 위치(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(n: Int, m: Int): List<List<Int>> {
        val results = mutableListOf<List<Int>>()
        val currentPermutation = mutableListOf<Int>()
        // 1부터 n까지의 숫자 사용 여부를 저장할 배열
        val used = BooleanArray(n + 1) { false }
        
        backtrack(n, m, currentPermutation, used, results)
        
        return results
    }

    fun backtrack(
        // 현재 상태
        n: Int,
        m: Int,
        currentPermutation: MutableList<Int>,
        used: BooleanArray,
        // 탐색을 하며 찾은 정답을 저장할 저장소
        results: MutableList<List<Int>>
    ) {
        // 1. 종료 조건
        // 현재 순열의 길이가 m과 같을 경우
        if (currentPermutation.size == m) {
            results.add(ArrayList(currentPermutation))
            return
        }
        
        // 2. 재귀 호출
        // 1부터 n까지의 모든 숫자를 탐색
        for (i in 1..n) {
            // 상태 확인 (가지치기)
            // 현재 숫자를 사용할 수 있는지 확인
            if (isPromising(i, used)) {
                // 상태 변환 (전이)
                currentPermutation.add(i)
                used[i] = true
                
                // 탐색 진행
                backtrack(n, m, currentPermutation, used, results)

                // 백트랙
                
                // 상태 되돌리기
                currentPermutation.removeAt(currentPermutation.size - 1)
                used[i] = false
            }
        }
    }

    // 현재 숫자를 사용할 수 있는지 확인
    fun isPromising(
        i: Int,
        used: BooleanArray
    ): Boolean {
        // 이미 사용한 숫자인지 확인
        if (used[i]) {
            return false
        }
        return true
    }
}

fun main() {
    val n = 3 // 1부터 3까지의 자연수
    val m = 2 // 2개를 선택
    val solution = solution()
    val result = solution.permutations(n, m)
    result.forEach {
        println(it.joinToString(" ")) // 각 순열 출력
    }
}

문자열 조합 문제

• https://leetcode.com/problems/letter-combinations-of-a-phone-number

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)
}