✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘
소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는Kotlin을 기반으로 작성하였습니다.
들어가기 전
완전 탐색 알고리즘은 가능한 모든 경우의 수를 직접 확인하는 방식입니다.
그래서 구현이 직관적이고, 정답을 빠뜨리지 않는다는 장점이 있습니다.
다만 완전 탐색은 모든 경우를 전부 확인해야 하기 때문에,
입력 크기가 커질수록 시간 복잡도가 급격히 증가할 수 있습니다.
여기서 한 가지 주의할 점은, 완전 탐색의 시간 복잡도가 항상 O(N)인 것은 아니라는 점입니다.
문제에 따라 O(N²), O(2^N), O(N!)처럼 훨씬 더 커질 수도 있습니다.
즉, 핵심은 확인해야 하는 경우의 수가 많아질수록 비효율적일 수 있다는 점입니다.
이럴 때 사용할 수 있는 대표적인 방법이 바로 백트래킹(Backtracking)입니다.
백트래킹
백트래킹은 완전 탐색의 한 종류이며,
불필요한 경우를 미리 제외하면서 탐색을 진행하는 알고리즘입니다.
완전 탐색이 가능한 모든 경우를 끝까지 확인한다면,
백트래킹은 탐색 도중 이미 조건에 맞지 않는 경우를 발견했을 때
그 경로를 더 이상 진행하지 않고 바로 되돌아갑니다.
즉, 백트래킹의 핵심은 다음과 같습니다.
- 가능한 경우를 탐색한다.
- 현재 선택이 조건에 어긋나면 더 깊이 들어가지 않는다.
- 이전 단계로 돌아가 다른 선택지를 시도한다.
이처럼 더 볼 필요가 없는 가지를 미리 잘라내는 것을
보통 가지치기(pruning)라고 합니다.
완전 탐색과의 차이
완전 탐색은 가능한 모든 경우를 끝까지 확인합니다.
반면 백트래킹은 조건에 맞지 않는 경우를 발견하면 그 즉시 돌아갑니다.
즉, 백트래킹은 완전 탐색보다 항상 다른 알고리즘이라기보다는
완전 탐색을 더 효율적으로 수행하는 방식에 가깝습니다.
보통은 재귀 함수와 DFS(깊이 우선 탐색) 형태로 구현합니다.
현재 상태에서 가능한 선택지를 하나 고르고,
조건에 맞는 경우에만 다음 단계로 내려가는 방식입니다.
다만 백트래킹이 항상 시간 복잡도를 크게 줄여 준다고 단정할 수는 없습니다.
최악의 경우에는 여전히 많은 경우를 확인해야 할 수도 있습니다.
하지만 실제 문제에서는 가지치기를 잘 활용하면
탐색해야 하는 경우를 크게 줄일 수 있습니다.
예를 들면
다음과 같은 2차원 배열이 있다고 가정해 보겠습니다.
이 행렬에서 숫자 3개를 선택하되,
선택한 숫자들의 행과 열이 모두 서로 달라야 한다고 해보겠습니다.
즉,
- 각 행에서는 하나씩만 선택할 수 있고
- 이미 선택한 열은 다시 선택할 수 없습니다
이때 가능한 선택 과정을 트리 형태로 그려 보면 다음과 같이 볼 수 있습니다.
이처럼 각 단계에서 선택 가능한 열을 하나씩 고르면서 내려가다가,
이미 사용한 열을 다시 선택해야 하는 상황이라면
그 경로는 더 이상 진행하지 않고 다른 경로를 탐색하면 됩니다.
이것이 바로 백트래킹의 전형적인 구조입니다.
in Kotlin
위 예시를 코드로 표현하면 다음과 같습니다.
fun main() {
val arr = listOf(
listOf(2, 4, 3),
listOf(1, 3, 7),
listOf(6, 5, 6)
)
val check = BooleanArray(3)
fun dfs(nums: List<Int>, row: Int) {
if (row == 3) {
nums.forEach { print("$it ") }
println()
return
}
for (col in 0..2) {
if (!check[col]) {
check[col] = true
dfs(nums + arr[row][col], row + 1)
check[col] = false
}
}
}
dfs(emptyList(), 0)
}이 코드의 흐름은 다음과 같습니다.
row는 현재 몇 번째 행을 선택 중인지 나타냅니다.check[col]은 해당 열을 이미 사용했는지 확인하는 배열입니다.- 아직 사용하지 않은 열이라면 선택하고 다음 행으로 이동합니다.
- 탐색이 끝나면 다시
false로 되돌려 다른 경우를 탐색합니다.
여기서 중요한 부분은 이 코드입니다.
check[col] = true
dfs(nums + arr[row][col], row + 1)
check[col] = false현재 열을 선택한 뒤 재귀 호출을 하고,
탐색이 끝나면 다시 선택을 해제합니다.
이렇게 해야 다른 경우의 수를 올바르게 탐색할 수 있습니다.
그리고 원래 코드에서는 row == 3일 때 출력만 하고 종료하지 않았기 때문에,
그 아래 반복문까지 실행되면서 인덱스 오류가 발생할 수 있었습니다.
그래서 반드시 return이 필요합니다.
실행 결과
코드를 실행하면 조건에 맞는 선택 결과들이 출력됩니다.
즉, 같은 열을 중복해서 사용하지 않으면서
각 행에서 하나씩 선택한 모든 경우를 확인할 수 있습니다.
이 결과는 앞에서 살펴본 가지 구조와 같은 흐름으로 탐색되며,
조건에 맞는 경우만 끝까지 내려가고 있다는 것을 보여 줍니다.
📌 결론
백트래킹은 완전 탐색 과정에서
조건에 맞지 않는 경로를 미리 제거하면서 효율적으로 답을 찾는 알고리즘입니다.
정리해 보면 다음과 같습니다.
- 백트래킹은 완전 탐색의 한 종류입니다.
- 모든 경우를 보되, 불가능한 경우는 중간에 탐색을 멈춥니다.
- 보통 재귀 함수와 DFS 형태로 구현합니다.
방문 배열,조건 검사,선택 후 복구가 핵심입니다.- 조합, 순열, N-Queen, 스도쿠 같은 문제에서 자주 등장합니다.
백트래킹은 처음 보면 단순한 재귀처럼 보일 수 있지만,
실제로는 “어디서 더 내려가지 말아야 하는지”를 판단하는 것이 핵심입니다.
즉, 단순히 깊이 들어가는 것이 아니라
불필요한 탐색을 얼마나 잘 줄이느냐가 중요한 알고리즘이라고 볼 수 있습니다.
