Backtracking

개념

가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘을 백트래킹 알고리즘이라고 한다.

해가 될 가능성이 없는 탐색 대상을 배제할 수 있으므로 완전 탐색하는 방법보다 효율적이다.

유망 함수

백트래킹 알고리즘의 핵심은 '해가 될 가능성을 판단하는 것'이다. 가능성은 유망 함수라는 것을 정의하여 판단한다.

백트래킹 알고리즘은 다음과 같은 과정으로 진행한다.

1. 유효한 해의 집합을 정의한다.

2. 위 단계에서 정의한 집합을 그래프로 표현한다.

3. 유망 함수를 정의한다.

4. 백트래킹 알고리즘을 활용해서 해를 찾는다.

문제 1. 피로도

설명

든든앤파이터라는 게임에는 피로도 시스템이 있습니다. 피로도는 정수로 표시하며 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 각 던전마다 탐험을 시작하기 위해 필요한 최소 필요 피로도와 던전 탐험을 마쳤을 때 소모되는 소모 피로도가 있습니다. 예를 들어 최소 필요 피로도가 80, 소모 피로도가 20인 던전을 탐험하기 위해서는 현재 남은 피로도는 80 이상이어야 하고, 던전을 탐험한 후에는 피로도 20이 소모된다. 이 게임에는 하루에 한 번만 탐험할 수 있는 던전이 여러 개 있습니다. 한 유저가 오늘 던전을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 최소 필요 피로도, 소모 피로도가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때 유저가 탐험할 수 있는 최대 던전 수를 반환하는 solution() 함수를 완성하세요.

제약 조건

• k는 1 이상 5,000 이하인 자연수입니다.

• dungeons의 세로 길이, 즉 던전 개수는 1 이상 8 이하입니다.

  • dungeons의 가로 길이는 2입니다.

  • dungeons의 각 행은 각 던전의 [최소 필요 피로도, 소모 피로도]입니다.

  • 최소 필요 피로도는 항상 소모 피로도보다 크거나 같습니다.

  • 최소 필요 피로도와 소모 피로도는 1 이상 1,000 이하인 자연수입니다.

  • 서로 다른 던전의 [최소 필요 피로도, 소모 피로도]가 같을 수 있습니다.

입출력의 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

코드

fun main() {
    fun solution(k: Int, daungeons: Array<IntArray>): Int {
        var result = 0

        fun visitDaungeon(fatigue: Int, daungeonInfo: IntArray, daungeonIndex: Int, count: Int, visit: IntArray) {
            val visited = visit.clone()
            //   1.1.1 현재 피로도로 현재 방문한 던전을 돌 수 있는지 확인한 후 돌지 못 할 경우 함수를 종료한다.
            if (fatigue < daungeonInfo[0]) {
                return
            }
            //   1.1.2 현재 던전을 방문 여부에 넣는다.
            visited[daungeonIndex] = 1
            //   1.1.3 결과에 1을 더한다.
            val visitedCount = count + 1
            //   1.1.4 현재 피로도에서 던전의 소요 피로도를 뺀다.
            val spentFatigue = fatigue - daungeonInfo[1]
            //   1.1.5 던전들에서 아직 방문하지 않은 던전을 찾아서 돈다.
            for (i in daungeons.indices) {
                if (visited[i] == 1) continue
                visitDaungeon(spentFatigue, daungeons[i], i, visitedCount, visited)
            }
            //   1.1.6 방문하지 않은 던전이 없을 경우 현재 방문 횟수가 결과 횟수보다 크면 결과 횟수를 변경한다.
            if (result < visitedCount) {
                result = visitedCount
            }
            //   1.1.7 함수를 종료한다.
            return
        }

        // 1. 각 던전을 순회한다.
        for (i in daungeons.indices) {
            //  1.1. 재귀 함수 호출
            visitDaungeon(k, daungeons[i], i, 0, IntArray(daungeons.size))
        }

        return result
    }

    val k = 80
    val daungeons = arrayOf(intArrayOf(80, 20), intArrayOf(50, 40), intArrayOf(30, 10))
    println(solution(k, daungeons))
}

문제 2. N-퀸

설명

가로, 세로 길이가 n인 정사각형 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 체스판의 길이 n이 주어질 때 조건을 만족하는 퀸 배치 수를 반환하는 solution() 함수를 완성하세요.

제약 조건

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.

• n은 12 이하의 자연수입니다.

입출력의 예

n	result
4	2

코드

참고

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=kotlinschool.programmers.co.kr

피로도

https://school.programmers.co.kr/learn/courses/30/lessons/12952school.programmers.co.kr

N-퀸