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

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

2112. (모의 SW 역량테스트) 보호 필름
문제의 저작권은 SWEA에 있습니다

 

---

초기 접근 방법

처음에는 부분집합의 개수로 접근을 하고, 만들어진 부분집합으로 조합을 만들고 나서
약품주입 및 품질확인 과정을 진행한 뒤에 최소 주입횟수를 갱신시켜주는 방법을 사용하였다.
이 방법은, 내가 부분집합을 구하는 방법에서 가장 작은 개수부터 생성되는 것이 아니었기에((1) (1,2) (1,3) (1,2,3) (2)...)
최소 주입횟수를 갱신하는데 까다로운 면이 있었다.

최종 접근 방법

완전탐색으로 접근하면 가능은 하겠지만, 그것보다는 더 파워풀하게 접근해보자.
tArr(초기 행 저장 배열)을 적극 활용한다면(초기 접근에서도 사용은 했지만 복잡하게 꼬였다) 이상적일 것이다.

1. 약품을 주입하지 않고 다음 행으로 재귀.
2. 현재 열(idx)을 복사(tArr)
3. 현재 열을 0으로 바꾸고 재귀.
4.  현재 열을 1으로 바꾸고 재귀.
5. 복사했던 열(tArr) 원상복귀.
   여기서 핵심 기저조건은, 재귀를 돌 때의 주입횟수가 ans(기록된 최저 주입 횟수)보다 크거나 같아진다면 의미가 없기 때문에,
   바로 return;을 해줌으로써 프루닝을 해준다.
   이 생각을 하기 전에는 K(충족해야할 셀의 개수)를 기준으로 프루닝을 하려고 했지만,
   현재 ans를 기준으로 하는 것이 더 많은 시간과 메모리를 아낄 수 있다고 생각했다.
   그리고 나서, 최종열까지(idx가 R과 같아진다면) 확인을 했다면, 거기서 품질체크를 해주고 조건을 만족한다면
   ans를 주입횟수의 최소값과 비교해서 갱신해준다.

   ---

   
   요즘 푸는 문제들이 결국은 백트래킹으로 마무리된다.
   백트래킹을 아주 조금은 알고있었고, 개념도 이해했지만 한번에 개념을 적용하기에는 아직 많이 부족하고 미흡함을 느꼈다.
   최종 코드를 보면, 백트래킹이 굉장히 파워풀하고 코드를 이해하는데에도 직관적이라 좋다는 것을 느끼지만
   한번에 접근해서 문제를 풀 수 있도록 더 노력해야겠당!
   끗-!

import java.util.Scanner;
 
public class swea_2112_보호필름2 {
 
    static int K;
    static int R;
    static int C;
    static int[][] map;
    static int ans;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            R = sc.nextInt();
            C = sc.nextInt();
            K = sc.nextInt();
            map = new int[R][C];
            ans = 987654321;
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            dfs(0,0);
            System.out.println("#" + tc + " " + ans);
        } // end test cases
    }// end main
 
    
    static void dfs(int idx, int inject) {
        // 주입횟수가 현재 최저투입횟수보다 크면 확인해볼 필요가 없음.
        if(inject >= ans) return;
        
        // 가장 아래까지 row(D)갔다면
        if(idx >= R) {
            //검사에 통과하는지 확인 
            if(check_Quality()) {
                ans = Math.min(ans, inject);
            }
            return;
        }
        
        // 아무 약품도 주입하지 않고 pass
        dfs(idx+1, inject);
        
        // 원본(초기)값 저장하기 
        int[] tArr = new int[C];
        for(int i=0; i<C; i++)
            tArr[i] = map[idx][i];
        
        // 현재 idx(row,D)에 0을 주입하고 재귀.
        for(int i=0; i<C; i++)
            map[idx][i] = 0;
        dfs(idx+1, inject+1);
        
        // 현재 idx에(row,D)에 1을 주입하고 재귀.
        for(int i=0; i<C; i++)
            map[idx][i] = 1;
        dfs(idx+1, inject+1);
        
        // 원본(초기)값으로 되돌리기.
        for(int i=0; i<C; i++)
            map[idx][i] = tArr[i];
    }
    
    static boolean check_Quality() {
        for (int i = 0; i < C; i++) {
            int cnt = 1;
            int flag = 0;
            for (int j = 0; j < R - 1; j++) {
                if (map[j][i] == map[j + 1][i]) {
                    cnt++;
                } else
                    cnt = 1;
                // 해당 컬럼은 K를 만족. 다음 컬럼으로 이동.
                if (cnt >= K) {
                    flag = 1;
                    break;
                }
            } // end for j
                // 단 하나의 컬럼에서도 K미만이면 안됨.
            if (flag == 0)
                return false;
        } // end for i
        return true;
    }// end check_Quality method
}