코딩 테스트 합격자 되기 스터디 7주차 : 백트래킹

백트래킹

백트래킹 개념

• 가장 최근에 방문했던 노드로 다시 돌아감(DFS)
• 완전 탐색하지 말고, 내가 찾는 답일 가능성이 있는 경우에만 탐색한다.

왜 백트래킹인가?

어느 날 집을 떠나 외출한 후, 중요한 물건을 집에 놓고 왔다는 생각이 들었다. 이 상황에서 물건을 찾기 위해 모든 아파트를 탐색해야 할까? 아니면 먼저 우리 집만 탐색하는 것이 합리적일까?

물건을 우리 집에 놓고 왔다고 판단하는 순간, 다른 아파트를 모두 탐색할 필요가 없다는 결론에 도달한다. 이처럼 문제 해결 과정에서 가능성이 없거나 불필요한 경로를 일찍 차단하고, 유망한 경로만 탐색하는 것이 바로 백트래킹이다.

유망함수란?

백트래킹에서 중요한 개념 중 하나는 유망함수이다. 유망함수는 특정 경로가 문제의 해답이 될 가능성이 있는지를 평가하는 기준을 제공하는 함수이다. 다시 말해, "우리 집에 물건을 놓고 왔을 가능성이 있다"고 판단하는 것처럼, 어떤 경로를 계속 탐색할 가치가 있는지, 아니면 그만두고 다른 경로를 시도해야 하는지를 결정하는 역할을 한다.

유망함수의 역할

예를 들어, 방대한 아파트 단지에서 잃어버린 물건을 찾는다고 생각해보자. 이때 유망함수는 "물건을 놓고 왔을 가능성이 높은 장소"를 판단하는 기준이 된다. 우리 집에서 물건을 놓고 왔을 가능성이 높다고 판단되면, 먼저 우리 집을 탐색하고, 그 결과에 따라 다음 행동을 결정한다. 만약 다른 아파트에서 물건을 찾을 가능성이 거의 없다고 판단된다면, 굳이 다른 아파트를 탐색할 필요가 없다는 결론을 내릴 수 있다.

백트래킹의 효율성

백트래킹의 강점은 바로 이 유망함수를 통해 불필요한 탐색을 최소화하고, 문제를 효율적으로 해결할 수 있다는 점이다. 유망하지 않은 경로를 일찍 배제하고, 유망한 경로만을 탐색함으로써 탐색의 범위를 좁히고 시간과 자원을 절약할 수 있다.

백트래킹을 활용하면, 문제의 해결 방법이 여러 가지인 경우에도 최적의 해결책을 찾는 데 도움이 된다. 복잡한 문제를 효율적으로 풀기 위해서는 유망함수를 잘 설계하는 것이 매우 중요하다.

• 가능성이 없는 곳은 들어갔다가 다시 돌아감 (백트래킹)
• 가능성이 있는 곳을 탐색

백트래킹 푸는 과정

상태 정릐

문제의 각 단계에서 가능한 상태를 정의

유망 함수

현재 상태가 유망한지 판단, 유망하지 않으면 더 이상 탐색하지 않음

해결책 확인

현재 상태가 문제의 해결책인지 판단

재귀 호출

유망한 상태로 이동하면서 문제 해결

백 트래킹 예시

부분 집합(부분 합)

• 노드 안에 숫자는 합을 뜻함
• 합이 5인 조합은 [1, 4], [2, 3] 이다.

문제
{1, 2, 3, 4}로 이루어진 집합에서 숫자를 뽑아서 합의 5인 조합 구하기

완전 탐색으로 풀기

• 각 집합은 뽑는다, 뽑지 않을 수 있으므로, 아래와 같음
• 완전 탐색 시간복잡도는 O(N^2)이므로 효율적이지 않다.

부분합을 백트래킹으로 접근하기

• 상태 정의: 현재까지 선택한 숫자들의 합
• 유망 함수:
  • 조건 수립
  • 현재 부분 합이 목표 값을 초과하면 유망하지 않다고 판단
• 해결책 확인 : 현재 부분 합이 목표 값과 일치하는 확인
• 재귀 호출

백트래킹 예시(부분 합)

백 트래킹으로 풀기

• 현재 조합으로 합의 5가 되면 더이상 탐색할 필요가 없음(isSolution == true)
• 해당 숫자를 조합하여 합이 K 이상이 되면 탐색할 필요가 없음(isPromising == false)

N Queen

N Queen을 백트래킹으로 접근하기

• 상태정의: 각 행에 하나의 퀸이 위치하도록 함
• 유망 함수: 현재 행에 퀸을 놓았을 때, 다른 퀸과 충돌하는지 확인
• 해결책 확인: 모든 퀸이 배치되었는지 확인
• 재귀 호출: 다음행에 퀸을 배치

아이디어1

• 각 행의 동일한 열에 퀸이 배치되지 않도록 함
  • 각 열의 값이 같은지 확인

아이디어2

• 각 행의 오른쪽 방향 대각선에 같은 퀸들이 겹치지 않도록 함
  • 행과 열의 차가 같은지 확인
• 각 행의 왼쪽 방향 대각선에 같은 퀸들이 겹치지 않도록 함
  • 행과 열의 절대값 차가 같은지 확인

추천 문제

피로도

package hyojin.etc.백트래킹;

public class DungeonExploration {
    private static int maxDungeonCount = 0;

    public static void main(String[] args) {
        int k = 80;
        int[][] dungeons = {{80, 20}, {50, 40}, {30, 10}};

        System.out.println(solution(k, dungeons)); // 예상 출력: 3
    }

    public static int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        exploreDungeons(k, dungeons, visited, 0);
        return maxDungeonCount;
    }

    private static void exploreDungeons(int currentFatigue, int[][] dungeons, boolean[] visited, int count) {
        // 현재 탐험한 던전 수(count)와 비교해 최대 던전 수 갱신
        maxDungeonCount = Math.max(maxDungeonCount, count);

        // 모든 던전을 순회하면서 탐험 가능 여부 확인
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && currentFatigue >= dungeons[i][0]) { // 방문하지 않은 던전이고, 최소 피로도 조건을 만족하면
                visited[i] = true; // 던전을 탐험했다고 표시
                exploreDungeons(currentFatigue - dungeons[i][1], dungeons, visited, count + 1); // 던전을 탐험한 후 다음 단계로 진행
                visited[i] = false; // 탐험을 마치고 다음 경우의 수를 위해 원상태로 돌려놓음
            }
        }
    }
}

출처

코딩 테스트 합격자 되기 - C++