[묘공단] 코딩 테스트 합격자 되기 - 백트래킹

코딩 테스트 합격자 되기 자바편

책 제목 : 코딩 테스트 합격자 되기 자바편

지은이 : 김희성

 

깊이탐색과 너비탐색의 문제

깊이와 너비 우선 탐색 방법은 완전 탐색이라고한다.

완전 탐색의 경우 모든 경우의 수를 탐색하는 방법이므로 대부분의 경우 비효율적이다.

 

백트래킹 예시

예를 들어 우리가 출근하기 위해 아파트를 나섰는데 지갑을 두고와서 집으로 되돌아갈때 방을 하나씩 보면서 물건을 찾는다.

화장실, 베란다, 거실등을 순서대로 볼때 지갑이 없을 가능성이 있는곳은 알아보고 되돌아가는 것을 백트래킹이라 한다.

 

백트래킹 알고리즘의 핵심은 해가 될 가능성을 판단하는 것이다.

진행과정

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

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

3. 유망 함수를 정의합니다.

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

유망함수

주로 유망함수를  사용하는데 유망함수란 해가 될 가능성을 판단하는 것 이다.

 

예시 )

숫자 두개를 뽑아서 7을 만드는 경우의 수를 찾는다.

숫자배열에는 [1,2,3,4]가 있다고 가정한다.

 

처음 뽑은 숫자가 3미만이면 답이 나올수 없으므로 시작점으로 돌아가는(백트래킹) 전략을 사용한다.

예시 문제

1 ~ N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환하는 solution()함수를 작성하세요.

 

조건

1. 백트래킹을 활용해야한다

2. 숫자 조합은 오름차순으로 정렬되어야한다.

3. 같은 숫자는 한번만 선택할 수 있다.

4. N은 1이상 10이하의 정수이다.

import java.util.ArrayList;

class Solution {

    private static ArrayList<ArrayList<Integer>> result;

    private static int n;

    private static void backtrack(int sum, ArrayList<Integer> selectedNums, int start) {

        // 합계가 10이 되면 담는다.
        if (sum == 10) {
            result.add(selectedNums);
            return;
        }

        for (int i = start; i < n; i++) {
            // 누적 합이 10보다 작으면 값을 더하면서 재귀 호출
            if (sum + i <= 10) {
                ArrayList<Integer> list = new ArrayList<>(selectedNums);

                list.add(i);
                // 백트래킹 메서드를 재귀적으로 호출
                backtrack(sum + i, list, i + 1);
            }
        }
    }

    public static void main(String[] args) {
        result = new ArrayList<>();

        // 입력 값
        n = 5;

        backtrack(0, new ArrayList<>(), 1);

        System.out.println(result);
    }
}