[백준] 16637.괄호 추가하기 (java) / DFS, 백트래킹, 조합, 시뮬레이션

@DFS, 백트래킹, 조합, 시뮬레이션 / 3h 이상

간단한 문제라고 생각했는데, 조합에서 한번 헤매고, 계산하는 곳에서 한번 더 헤매서

처음 맞았을때는 도대체 왜 맞는지도 이해가 안됐었다.

재귀를 이용한 DFS 백트래킹 조합을 공부하는 기회가 됐다.

 

 

구현 방법

DFS, 백트래킹을 이용한 조합 구현

1. 괄호를 놓을 수 있는 곳은

 3+ 8* 7- 9*2

이 네 곳(== 배열크기 N / 2)이다.

 

그런데 빨간 칸에 연속해서 괄호를 배치할 수는 없으므로,

괄호 개수를 0부터 - 가능한 최대 개수 까지 놓되,

인접한(붙어있는) 칸은 뽑지 않는 조합을 구하기로 했다.

 

 

2. 그런데 이 조합을 구하는게 생각보다 너무 어려워서, 결국 실패하고 도움을 받았는데,

바로 이 방법이다. (더 나은 방법은 4번 참고)

 

1) 이번 턴은 뽑지 않고, 다음 턴으로 그냥 넘어간다
2) 이번 턴을 뽑고, 다다음턴으로 바로 넘어간다 (다음 턴은 어차피 뽑을 수 없으므로)

dfs(int idx) {
	if (idx >= size + 2) return;
    
    if (idx == size || idx == size + 1) {
    	함수;
        return;
	}
    
    //이번 턴은 뽑지 않고, 다음 턴으로 그냥 넘어간다
    dfs(idx + 1);
    
    //이번 턴을 뽑고, 다다음턴으로 바로 넘어간다 (다음 턴은 어차피 뽑을 수 없으므로)
    permu[idx] = true;
    dfs(idx + 2);
    permu[idx] = false;
}

 

그런데 이 방법은, 다다음 턴으로 넘어가는 경우까지 고려해서 종료 조건을 다르게 설정해야 했는데,

이해는 되지만 시험장 가서 짤 자신이 없어서. 선생님께 도움을 요청했다.

 

 

3. 더 쉬운 방법

일단 무조건 한턴씩 진행한다. → 종료 조건이 간단해진다.

그리고 뽑을 지 말지에 대해서는 이전 턴에서 뽑았는지 여부로 판단한다.

 

판단 방법은 이 둘중 하나를 쓰면 된다.

1) 배열의 인덱스를 사용해서 이전 인덱스에서 뽑았는지를 체크하거나

2) 매개변수로 이전에 뽑았는지를 들고다닌다

 

그런데 배열의 인덱스를 사용하면 첫 턴이 애매해진다(첫 턴은 이전 인덱스가 없으니까)

그래서 이 때는 매개변수로 (첫 시작 인덱스인 0, 뽑지 않았다는 의미의 false)를 넘기면 효율적이다.

 

 

단, 매개변수는 너무 많이 들고다니면 스택에 무리가 갈 수 있음을 유의하자

(그런데 알고리즘 말고 일반 개발에서는 전역변수는 최대한 지양하고, 매개변수를 사용하는게 좋다.)

dfs(int idx, boolean prevSelect) {
	if (idx == size) {
    		함수;
		return;
	}
    
    //이전 턴에 뽑지 않았다면 이번 턴에 뽑기
    if (!prevSelect) {
    	permu[idx] = true;
        dfs(idx + 1, true);
        permu[idx] = false;
    }
    
    //이전 턴에 뽑았든 안뽑았든 이번 턴에는 안뽑기
    dfs(idx + 1, false);
}

 

이전 턴에 안뽑았다면 1)이번턴에는 뽑거나 2)이번턴에도 안뽑을 수 있고

이전 턴에 뽑았다면 1)이번턴에는 안뽑아야 한다

 

즉, 이전 턴의 선택과 상관 없이 이번 턴에 안뽑는건 항상 가능하다.

그러므로, 이번 턴에 뽑을 경우에만 조건을 주고, 이번 턴에 뽑지 않는 경우에는 조건을 주지 않는다.

 

 

 

수식 계산 부분

1. 3+8*7-9*2 가 예제로 주어져 있는데

이를 num배열 3 8 7 9 2 (배열크기 N / 2 + 1) 과

operation배열 + * - * (배열크기 N / 2) 로 분리해서 생각했다.

 

 

2. 위에서 뽑은 permu 배열(배열크기 N / 2, 여기서는 4)을 기준으로 괄호 안의 값을 먼저 계산한다.

예를들면 permu배열에 true, false, true, false가 담겨 있으면

(3+8)*(7-9)*2

이렇게 계산한다.

 

 

3. 일단 temp배열에 num배열의 값을 복사해둔다.

그리고 if(permu[i])일 경우 temp[i]는 0으로, temp[i + 1]은 계산한 결과를 담아준다.

0으로 만들어 준 부분은 계산하지 않도록 visit을 true로 체크해준다

num	3	8	7	9	2
temp	0	11	0	-2	2
visit	true	false	true	false	false
operator	+	*	-	*	없음

 

 

4. 처음에는 visit배열의 사이즈를 operator 사이즈와 같게 해서 마지막 값이 계산되지 않았는데,

어차피 false면 계산되지 않아서 visit 배열 크기를 1 키워줬더니 문제 없이 돌아갔다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	private static int size, maxRslt = Integer.MIN_VALUE, num[];
	private static char operator[];
	private static boolean permu[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		size = N / 2;
		
		num = new int[size + 1];
		operator = new char[size];
		permu = new boolean[size];
		String temp = br.readLine();
		for (int i = 0; i < N; i++) {
			if (i % 2 == 0)num[i / 2] = temp.charAt(i) - '0';
			else operator[i / 2] = temp.charAt(i);
		}
		
		if (N == 1) {
			System.out.println(num[0]);
			return;
		}
		dfs(0);
		System.out.println(maxRslt);
	}

	private static void dfs(int idx) {
		if (idx > size + 1) return;
		
		if (idx >= size) {
			int rslt = calc();
			if (maxRslt < rslt) maxRslt = rslt;
			return;
		}
		//이번 턴에는 안뽑고 다음턴으로 넘어간다 
		dfs(idx+1);
		
		//뽑고 다다음턴으로 넘어간다 (어차피 이번턴에 뽑으면 다음 턴에는 못 뽑음) 
		permu[idx] = true;
		dfs(idx+2);
		permu[idx] = false;
	}

	private static int calc() {
		int[] temp = num.clone();
        //visit 사이즈 하나 크게 해주는게 핵심!
		boolean[] visit = new boolean[size + 1];
		
		int rslt = 0;
		boolean init = true;
		
		for (int i = 0; i < size; i++) {
			if (permu[i]) {
				temp[i] = 0;
				temp[i + 1] = switchs(num[i], num[i + 1], operator[i]);
				visit[i] = true;
				i++;
			}
		}

		int prev = 0;
		for (int i = 0; i < size + 1; i++) {
			if (init) {
				if (!visit[i]) {
					rslt = temp[i];
					init = false;
					prev = i;
				}
			}
				
			for (int j = i + 1; j < size + 1; j++) {
				if (!visit[j]) {
					rslt = switchs(rslt, temp[j], operator[prev]);
					i = j - 1;
					prev = j;
					break;
				}
			}
		}
		return rslt;
	}

	private static int switchs(int a, int b, char op) {
		switch (op) {
		case '+': return a + b;
		case '-': return a - b;
		case '*': return a * b;
		}
		return 0;
	}
}

힘들었다..ㅎㅎ

힘들었지만 많은 걸 배울 수 있었던 문제였다.

 

끝!

 

17547748 망한 코드

17576732 calc 계산식만 고친 코드

...

17576977 dfs 개선 + 종료 조건 간소화 한 코드