[SWEA] 2112. [모의 SW 역량테스트] 보호 필름

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

SW Expert Academy

Fail을 엄청 많이 한 문제였다ㅠㅠ 심지어 이번에 다시 풀어본 것임에도 불구하고 4번 만에 Pass 했다...

보호 필름 문제는 dfs를 사용하여 각 막에 약물 A를 투여하는 경우, B를 투여하는 경우, 약물을 투여하지 않는 경우를 모두 구해줬다.

 

이 문제에서주의할 점은 합격 기준인 K가 1인 경우다.

K가 1인 경우 무조건 합격이므로 검사를 해줄 필요 없이 바로 0을 출력해주어야 한다.

 

완전 탐색

먼저 K==1 인 경우에는 0을 출력해주도록 처리하고 바로 다음 테스트 케이스로 넘어간다.

K가 1보다 큰 경우에는 각 막에 약품을 투여하여 변경된 상태를 새로 적용해주기 위해서 매번 새로운 배열을 만들어주었다.(메모리를 많이 써서 다른 방법을 쓰는 게 좋을 것 같다...)

현재 투여한 약물의 수가 이미 기준을 통과한 최솟값을 넘어간다면 더 검사할 필요가 없으므로 return 하도록 백트래킹을 해준다.

매번 dfs에서는 합격하는지 검사해주고 기준을 통과했다면 min값을 바꾸고 return 한다.(통과한 시점에서 더 많은 약물을 투여할 필요가 없기 때문)

모든 막에 대한 약물 투여 여부를 결정해준 경우에도 return.

 

합격 기준 검사

합격 기준을 검사하는 부분에서는 모든 열에 대해서 합격 기준을 통과하는지 검사해준다.

하나의 열이라도 합격기준을 통과하지 못하면 합격하지 못한다.

각 열에 대해서는 연속하는 K개의 셀이 같은 값인지 검사해주고 한 번이라도 그러한 경우가 있다면 다음 열의 검사로 넘어간다.

 

import java.io.*;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int D,W,K, min;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            int[][] film = new int[D][W];
            for(int i=0; i<D; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<W; j++) {
                    film[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
 			
            //합격 기준이 1인 경우 바로 0을 출력하고 다음 테스트 케이스로 넘어간다.
            if(K == 1) {
                System.out.println("#"+tc+" "+0);
                continue;
            }
             
             
            min = D+1; //약물을 투여하는 최대 개수는 D개이므로 적당히 D+1정도로 설정해주었다.
            dfs(film,0,0);
            System.out.println("#"+tc+" "+min);
        }
    }
     
    static void dfs(int[][] film, int index, int count) {
    	//현재 약품 투여 횟수가 이미 최솟값을 넘은 경우 더 검사할 필요가 없으므로 return
        if(count >= min) return; 
        
        
        //합격 기준을 통과한 경우 최솟값을 count값(현재 약품 투여 횟수)으로 변경하고 return
        if(test(film)) {
            min = count;
            return;
        }
        
        
        //막의 범위를 넘어가는 경우 return
        if(index == D) return;
         
         
        //새로 넘겨줄 배열 생성
        int[][] arr = new int[D][W];
        for(int i=0; i<D; i++) {
            for(int j=0; j<W; j++) {
                arr[i][j] = film[i][j];
            }
        }
         
         
        //index행에 약품을 투여하지 않는 경우
        dfs(arr,index+1,count);
         
         
        //index행에 A약품을 투여하는 경우
        for(int j=0; j<W; j++) {
            arr[index][j] = 0;
        }
        dfs(arr,index+1, count+1);
        
        
        //index행에 B약품을 투여하는 경우
        for(int j=0; j<W; j++) {
            arr[index][j] = 1;
        }
        dfs(arr,index+1, count+1);
         
    }
     
    static boolean test(int[][] film) {
        boolean flag = false;
 
 		//모든 열을 검사 
        for(int j=0; j<W; j++) {
        
        	//각 열의 셀을 모두 검사 
            for(int i=0; i<=D-K; i++) {
                flag = true;
                
                //각 열에서 K개만큼의 연속적인 셀을 검사 
                for(int l=i+1; l<i+K; l++) {
                    if(film[i][j] != film[l][j]) {
                        flag = false; //K개만큼 연속적으로 같지 않으면 break 하고 밑의 셀부터 다시 검사 
                        break;
                    }
                }
                 
                //K개 연속적으로 같은 셀이 있으면 한 번이라도 있으면 이번 열은 바로 통과하고 다음 열로 넘어간다.
                if(flag) break;                 
            }
             
            //이번 검사한 열이 검사를 통과하지 못하므로 아예 테스트 통과 불가능 
            if(!flag) break;
        }
         
        if(!flag)
            return false;
        else
            return true;
    }
     
}