[SWEA] 2112. [모의 SW 역량테스트] 보호 필름(자바/DFS)

문제 접근 방법

문제 조건은 다음과 같습니다. 따라서, 저는 한 줄씩 A, B 두 가지 경우로 바꾸어보며 성능 검사를 통과하는 경우에는 재귀를 탈출시켰습니다. 이를 구현하기 위해 DFS를 사용하였습니다. 

조건 1

문제 풀이

1. DFS 기저 조건 : 모든 세로 줄에대한 성능 검사를 실시하여 전부 통과하는 경우 재귀를 탈출시킵니다.

2. A, B 투입하는 경우에 대한 경우의 수를 확인 후 값을 원상 복귀시켜야 합니다. 이를 위해 처음에 copyMaps라는 배열을 하나 만들어  maps[i] = Arrays.copyOf(copyMaps[i], W); 를 통해 값을 원복시켰습니다. 

3. 성능 검사 확인 method : 저는 성능 검사를 위해 메서드를 하나 만들었습니다. maps[r][c] 와 maps[r+1][c] 같이 연속적인 경우에 대해 같은 경우 카운트를 +1 시켜주었습니다. 그렇지 못한 경우에는 연속적으로 있어야 한다는 조건을 지키기 위해 다시 카운트를 시작하도록 했습니다.

 

public class Solution_2112 {
	
	static int D, W, K;
	static int result;
	static int[][] maps;
	static int[][] copyMaps;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			maps = new int[D][W];
			copyMaps = new int[D][W];
			
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) {
					maps[i][j] = copyMaps[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			result = K;
			
			if(K == 1) {
				result = 0;
				sb.append(String.format("#%d %d\n", tc, result));
				continue;
			}
			solve(0, 0);
			
			sb.append(String.format("#%d %d\n", tc, result));
		}
		System.out.println(sb);
	}
	
	//특성A는 0, 특성B는 1
	static void solve(int row, int cnt) {
		//기저조건 : 모든 세로 줄에 대해서 성능 검사
		if(check()) {
			result = Math.min(result, cnt);
			return;
		}
		
		if(cnt >= result) return;//가지치기
		
		
		//가로 줄에 대해 A,B로 바꾸어봄
		for (int i = row; i < D; i++) {
			
			Arrays.fill(maps[i], 0);
			solve(i+1, cnt+1);
			
			Arrays.fill(maps[i], 1);
			solve(i+1, cnt+1);
			
			maps[i] = Arrays.copyOf(copyMaps[i], W);
		}
	}
	
	//성능 검사를 진행한다.
	static boolean check() {
		for (int c = 0; c < W; c++) {
			int cnt = 1;
			boolean success = false;
			for (int r = 0; r < D-1; r++) {
				if(maps[r][c] == maps[r+1][c]) cnt++;
				else cnt = 1;//연속적이지 않은 경우 1로 세팅해 다시 카운트 시작하게 함
				
				if(cnt == K) {//성능 검사 통과
					success = true;
					break;
				}
			}
			if(!success) return false;
		}
		
		return true;
	}
	
	
	
}