[알고리즘 TIL] Q14888(백트래킹)

문제

https://www.acmicpc.net/problem/14888

트러블 슈팅

1. 순열 알고리즘

처음에는 순열을 어떻게 구현해야 할지 몰라 찾아보니, 백트래킹으로 가장 깔끔하게 구현할 수 있다는 것을 알게 되었다.
추가로 중복 순열을 구현하는 방법도 함께 익혔다.
두 알고리즘의 핵심적인 차이는 숫자를 사용했는지 여부를 체크하느냐에 있다.

// 1. 순열
static void permutation(int depth, int n, int r) {
    // 순열이 완성된 경우
    if(depth == r) {
        System.out.println(Arrays.toString(output));
        return;
    }

    // 0부터 n까지 반복
    for(int i = 0; i < n; i++) {
        // 방문하지 않은 값이면 넣기
        if(!visited[i]) {
            visited[i] = true;    // 방문 처리
            output[depth] = arr[i];    // 현재 depth를 인덱스로 사용
            permutation(depth + 1, n, r);    // depth + 1를 전달
            visited[i] = false; // 다음 순열을 뽑기위해 방문처리 제거
        }
    }
}

// 2. 중복 순열
static void repeatPermutation(int depth, int n, int r) {
	// 순열이 완성된 경우
	if (depth == r) {
		System.out.println(Arrays.toString(output));
		return;
	}

	// 0부터 n까지 반복
	for (int i = 0; i < n; i++) {
		output[depth] = arr[i]; // 현재 depth를 인덱스로 사용
		repeatPermutation(depth + 1, n, r); // depth + 1를 전달
	}
}

 

2. 백트래킹 구현

처음에는 백트래킹 함수에서 반복문의 횟수를 연산자의 개수 (N - 1)만큼 설정했다.
하지만 이렇게 하면 불필요하게 많은 중복 연산이 발생하여 결국 시간 초과로 이어졌다.

for (int i = 0; i < N-1; i++) {
            if (operatorCount[i] > 0) {
                operatorCount[i]--;
				...
                permutation(depth + 1, next);
                operatorCount[i]++;
            }
        }

문제를 해결하려면, 반복문의 범위를 가능한 선택지(연산자 종류 4개)로 한정해야 한다.

for (int i = 0; i < 4; i++) {  // 올바른 방식
    if (operatorCount[i] > 0) {
        operatorCount[i]--;
		...
        permutation(depth + 1, next);
        operatorCount[i]++;  // 백트래킹: 원상 복구
    }
}

 

백트래킹은 가능한 경우의 수만 탐색하도록 가지치기하는 탐색 방식이다. 이 문제에서는 가능한 경우의 수가 연산자 4종류뿐이므로, 해당 분기만 고려해야 한다.
또한, 탐색 후에는 반드시 상태를 원복해야 다음 경로를 정확하게 탐색할 수 있다.

이 문제를 통해 백트래킹의 구조를 완벽히 이해할 수 있었다. 

구현

import java.io.*;

public class Q14888 {
    static int N;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static int[] nums;
    static int[] operatorCount;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        nums = new int[N];

        String[] inputStrArr = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(inputStrArr[i]);
        }
        operatorCount = new int[4];
        inputStrArr = br.readLine().split(" ");
        for (int i = 0; i < 4; i++) {
            operatorCount[i] = Integer.parseInt(inputStrArr[i]);
        }

        permutation(0, nums[0]);
        bw.write(max + "\n");
        bw.write(min + "");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void permutation(int depth, int currentCalculateResult) {
        if (depth == N - 1) {
            if (max < currentCalculateResult) max = currentCalculateResult;
            if (min > currentCalculateResult) min = currentCalculateResult;
            return;
        }

        //연산자 개수(4)만큼 반복
        //백트래킹에서 반복문은 가능한 경우의 수에 대해 분기하는 것
        for (int i = 0; i < 4; i++) {
            if (operatorCount[i] > 0) {
                operatorCount[i]--;

                int next = 0;
                switch (i) {
                    case 0: next = currentCalculateResult + nums[depth + 1]; break;
                    case 1: next = currentCalculateResult - nums[depth + 1]; break;
                    case 2: next = currentCalculateResult * nums[depth + 1]; break;
                    case 3: next = currentCalculateResult / nums[depth + 1]; break;
                }

                permutation(depth + 1, next);
                operatorCount[i]++;
            }
        }
    }
}