맞춰봐 [백준 1248][JAVA][골드 3][백트래킹][DFS]

 

[광고 누르면 오늘의 행운 상승!!]

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

1248번: 맞춰봐

백트래킹 DFS문제

1. 참고사항 

- 중복순열을 이용하여 전부 돌리면 시간초과가 난다.
- 중복순열을 구해준 후에 판단하면 안되고 배열에 넣을때 유효한 값인지 판단해야한다.

2. 구현

- 2차원 map 배열에 들어오는 부호를 저장한다.
- dfs를 돌리면서 arr배열에 값을 채우는데 값을 채우고 check함수를 이용하여 검사한다.
- check 함수는 i번째부터 j번째까지의 구간을 더해가면서 map배열과 대조하여 맞는 부호면 진행하고
틀린 부호면 정지시킨다.

package Study6;

import java.io.*;
import java.util.*;

public class 맞춰봐 {

	static int N,ans;
	static int[] arr;
	static char[] ch;
	static char[][] map;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		ch = br.readLine().toCharArray();
		
		map = new char[N][N];
		int idx = 0;
		
		//map에 input을 저장한다 
		for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
            	map[i][j] = ch[idx++];
            }
        }
		
		arr = new int[N];
		dfs(0);
	}

	private static void dfs(int cnt) {
		if(cnt == N) {
			for (int i = 0; i < N; i++) {
				System.out.print(arr[i] + " ");
			}
			//바로 탈출한다.
			System.exit(0);
			return;
		}
		
		for (int j = -10; j <= 10; j++) {
			arr[cnt] = j;
			//백트래킹 : arr에 넣은 값이 유효한 값인지 판단
			if(check(cnt)) dfs(cnt+1);
		}
	}
	 private static boolean check(int idx) {
	        for (int i = 0; i <= idx; i++) {
	            int sum = 0;
	            for (int j = i; j <= idx; j++) {
	                sum += arr[j];
	                //map의 부호가 맞는지 검사한다.
	                if (map[i][j] != (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))) {
	                    return false;
	                }
	            }
	        }
	        return true;
	    }
}