[BOJ - JAVA] 14888 - 연산자 끼워넣기 (백트래킹)

# 주소

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

14888번: 연산자 끼워넣기

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
public class Main {
    static int n,m;
    static int[] arr;
    static int[] s;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static boolean[] visit = new boolean[n];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n];
        s = new int[4];
        for(int i = 0; i < n; i++){
            arr[i] = scan.nextInt();
        }
        for(int i = 0; i < 4; i++){
            s[i] = scan.nextInt();
        }
        sir(arr[0], 1);
        System.out.println(max);
        System.out.println(min);
    }
    public static void sir(int num,int count){
        if(count == n){
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }
        for(int i = 0; i < 4; i++){
            if(s[i] > 0){
                s[i]--;
                switch(i) {
                    case 0:
                        sir(num + arr[count], count + 1);
                        break;
                    case 1:
                        sir(num - arr[count], count + 1);
                        break;
                    case 2:
                        sir(num * arr[count], count + 1);
                        break;
                    case 3:
                        sir(num / arr[count], count + 1);
                        break;
                    s[i]++;
                }
            }
        }
    }
}

백트래킹의 기본중에 기본인 문제 아닐까 싶습니다.

사실 방문 인덱스도 따로 안구해줘도 되기 때문에 재귀함수의 개념만 이해하고 있어도 금방 풀리시지 않을까 싶습니다.

다만 주의하실 점이, arr의 크기는 n의 크기이지만 s의 크기는 덧셈, 뺄샘, 곱셈, 나눗셈 총 4가지이므로 s의 크기는  4가 되어야 합니다.

또한, 이 s[i]를 한 개씩 소모해주며 해당 인덱스를 switch문을 이용해, 재귀로 구현했습니다.

계속해서 s[i] 를 소모하다가 count = n이 되면 (n-1번 연산하면) 위로 올라가서 max와 min을 갱신합니다. 

 

왜 백트래킹을 시행을 하면 이 순서를 따로 섞지도 않았는데도 랜덤하게, 모든 경우에 대해 탐색이 가능할까요?

숫자 세개 1 2 3 4 이 있고, s의 배열이 {1,1,0,1}이라고 해봅시다.

그럼 제일 처음 백트래킹 구문을 실행하면, 1 + 2 - 3 / 4 = 0이 될 것 입니다.

그럼 일단 max 는 0이고 min도 0이겠군요.

이후, 재귀함수이기 때문에 이제서야 원래 실행되었던 sir문이 실행됩니다.

나눗셈의 break문 부터 실행되어 s[i]++ -> s[3] = 1이 되고, 두 번째 sir문이 종료되어 break가 시행되고 s[1]++됩니다.

마지막으로 첫 번째 시행했던 sir문도 종료되며 break가 시행되고 s[0]++됩니다.

그리고 여기서 끝나지 않습니다.

기존의 for문이 재실행 되어 (return되어) 다시 for문이 돌아갑니다.

그럼 아까 방문한 i를 건너 띄고 새로운 i에서 다른 인덱스를 방문하며 sir함수를 실행합니다.

그리고 다시 break가 되면서 s[i]를 또 돌려주고... 계속 반복하다보면 모든 경우의 수에 대해 로직을 짤 수 있게 되는데, 이렇게 간단한 for문과 if문, 재귀함수의 구현으로 완전 탐색이 가능하다는 것이 신기합니다.

이렇게 글로 쓰면서 설명하려 하니 더 어렵긴 하네요.

옛날에 블로그에 첫 백준 문제 게시글을 포스팅한게 N과 M시리즈였었는데 사실 그 때에도 머리로는 이해하는데 손이 도저히 이해가 안되어서 많이 헤맸던 기억이 납니다.

백트래킹에 대해서 지금도 완전히 100% 이해한 것은 아닙니다.

그러나, if문에서 count 개수 세는 것, for문과 dfs문 실행만으로도 전체의 경우의 수를 탐방할 수 있다는 것이 신기하네요.

다음 문제도 백트래킹으로 찾아뵙겠습니다.

감사합니다.