[SWEA] 2112. 보호필름

2212 보호필름

풀이)

재귀 + 브루트 포스 문제였다.

필름 막 상태를 vector<vector<int>> arr;에 저장해 놓았다.

그리고 약품으로 막 상태를 바꾼다면 기존의 값을 알아놔야하기 때문에

처음에는

vector<vector<int>> temp =arr; 로 전체 상태를 저장해놓은 뒤,

막 상태 바꾼 후 arr= temp; 로 돌려놓았는데 이렇게 하니 시간초과가 났다.

아무래도 백터 전체를 저장하고 돌려놓고 해서 그런듯 싶어

두번째로는 필름 막 상태 모두를 저장해놓지 않고,

기존의 막 상태(행)만 저장해두고 vector<int> temp = arr[i]; (i는 바꿀 막 인덱스)

상태 바꾼 후 원래 막 상태로 바꿔주도록 했더니 arr[i] = temp;

시간 초과가 나지 않고 통과했다. 

시간초과가 나지 않게 사용한 방법은 위에서 설명한 거 말고 2가지가 더있다.

1. k=1일때는 바로 0 출력

2. 성능 검사할 때, 열들을 계산하는데 이 때 해당 열에서 통과가 되면 바로 다음 열로 넘어간다.

막 상태 변경할때는 

예를 들어 두께가 5인 보호필름이 있고 k = 3이라면,

(편의상 인덱스를 1,2,3,4,5라고 하겠다)

1. 상태 한번 바꿈

1

2

3

4

5

2. 상태 두번 바꿈

1 -> 2

  -> 3

  -> 4

  -> 5

2 -> 3

  -> 4

  -> 5

.

.

.

3. 상태 세번 바꿈

1 ->2 -> 3

2 -> 4

2 -> 5

3 -> 4

3 -> 5

4 -> 5

2 ->3 -> 4

      3 -> 5

      4 -> 5

.

.

.

이런 식으로 상태를 몇 번 바꿀지, 

바꾼다면 어떤 막(= 행, column)을 바꿀지 while문을 통해 계속 확인해줬다.

행들을 바꿀 때마다 A상태, B상태 한 번씩다 바꿔서 확인해줬다.

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int d, w, k;
vector <vector<int>> arr;
bool result;
 
//성능검사하는 함수
void check() {
    bool fail = false;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < d; j++) {
            if (d - j < k) {
                fail = true;
                break;
            }
            int cnt = 1;
            for (int t = 1; t < k; t++) {
                if (arr[j][i] == arr[j + t][i]) {
                    cnt++;
                }
                else break;
            }
            if (cnt == k) break;
            
        }
        if (fail) break;
    }
 
    if (fail) return;
    else {
        result = true;
        return;
    }
}
 
void dfs(int row,int depth,int limit) {
    if (result) return;
    if (depth >= limit) {
        check();        
        return;
    }
    for (int i = row; i < d; i++) {
        vector<int> temp = arr[i];
        fill(arr[i].begin(), arr[i].end(), 0); //i번째 막을 A상태로
        dfs(i+1, depth + 1, limit);
        fill(arr[i].begin(), arr[i].end(), 1); //i번째 막을 B상태로
        dfs(i+1, depth + 1, limit);
        arr[i] = temp;
        if (result) return;
    }
}
 
int main() {
    freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    arr.resize(13);
    for (int i = 0; i < 13; i++) {
        arr[i].resize(20);
    }
    for (int test_case = 1; test_case <= T; test_case++) {
        //arr.clear();
        scanf("%d %d %d", &d, &w, &k);
        
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < w; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        if (k == 1) {
            printf("#%d 0\n", test_case);
            result = false;
            continue;
        }
        //약품투입안할때
        check();
        if (result) {
            printf("#%d 0\n", test_case);
            result = false;
            continue;
        }
        //투입할때
        int cnt = 1; //바꿀 막 개수
        while (true)
        {
            dfs(0, 0, cnt);
            if (result) break;
        
            cnt++;
        }
        printf("#%d %d\n", test_case, cnt);
        result = false;
    }
    return 0;
}