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

문제

SWEA 모의 SW 역량테스트 - 2112 보호 필름

SW Expert Academy

 

---

문제 풀이

접근 방식

이 문제는 주어진 보호 필름이 성능검사에 통과하기 위해 최소 몇 번의 약품을 투입해야 하는지 찾는 문제이다.

성능 검사는 보호 필름의 모든 세로 방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 존재해야 통과할 수 있고,

약품 투입을 하게 되면 해당 가로 방향이 모든 같은 특성으로 바뀌게 된다.

 

약품을 K회 투입하면 무조건 성능검사를 통과할 수 있다.

왜냐하면 같은 특성의 약품을 연속적으로  K회 넣어주면,

무조건 모든 세로 방향에 대해 동일한 특성의 셀이 K개 이상 연속되기 때문이다.

그래서 answer을 처음에 K로 설정해 놓고,

0회에서 최대 K-1회까지 약품을 투입해보며 더 낮은 횟수를 찾도록 구현하였다.

 

약품을 어느 막(행)에 어느 특성으로 넣을지를 결정하기 위해 DFS함수를 아래와 같이 구현하였다.

(change 벡터에 선택한 막의 인덱스와 특성을 넣어주었다.)

bool DFS(int start, int k) {
    int len = change.size();
    if (len == k) {
        for (auto i : change) {
            memset(film[i.first], i.second, sizeof(film[i.first]));
        }
        bool check = inspect();
        memcpy(film, film_copy, sizeof(film));
        return check;
    }
    for (int i = start; i < D; i++) {
            change.push_back({ i,0 });
            if (DFS(i + 1, k)) return true;
            change.pop_back();
            change.push_back({ i,1 });
            if (DFS(i + 1, k)) return true;
            change.pop_back();
    }
    return false;
}

 

위의 DFS 함수에서 선택한 막에 존재하는 셀을 모두 선택한 특성으로 바꿔주었고,

아래의 inspect 함수를 통해 선택한 조합으로 약품 투입 시, 성능 검사를 통과할 수 있는 지를 확인해주었다.

bool inspect() {
    for (int i = 0; i < W; i++) {
        int now = film[0][i];
        int count = 1;
        for (int j = 1; j < D; j++) {
            if (count == K) break;
            if (now == film[j][i]) count++;
            else {
                now = film[j][i];
                count = 1;
            }
        }
        if (count < K)
            return false;
    }
    return true;
}

 

DFS 함수를 재귀적으로 호출할 때, DFS함수의 매개변수로 (i + 1, k)를 넣어야 했는데

(start + 1, k)로 넣어서 시간 초과로 Fail을 했었다.

 

이를 깨닫지 못하고 다른 방식을 고민하다가,

약품을 투입할 막을 선택하고, 선택된 막에 모두 A를 넣어보고, 안되면 모두 B를 넣어보는 방식으로도 풀어보았다.

그 결과, 실행 시간은 45ms로 빨랐으나, 테스트 케이스 50개 중 49개만 통과되어 Fail을 하였다.

 

그래서 이 문제는 약품을 최소로 투입하기 위해 탐색해야 할 범위를 특정하고,

탐색할 모든 경우를 빠르고 정확하게 탐색하도록 구현하는 게 중요했던 거 같다.

---

풀이 코드 - C++

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
int D, W, K;
bool film[13][20];
bool film_copy[13][20];
vector<pair<int, bool>> change;
 
bool inspect() {
    for (int i = 0; i < W; i++) {
        int now = film[0][i];
        int count = 1;
        for (int j = 1; j < D; j++) {
            if (count == K) break;
            if (now == film[j][i]) count++;
            else {
                now = film[j][i];
                count = 1;
            }
        }
        if (count < K)
            return false;
    }
    return true;
}
 
bool DFS(int start, int k) {
    int len = change.size();
    if (len == k) {
        for (auto i : change) {
            memset(film[i.first], i.second, sizeof(film[i.first]));
        }
        bool check = inspect();
        memcpy(film, film_copy, sizeof(film));
        return check;
    }
    for (int i = start; i < D; i++) {
            change.push_back({ i,0 });
            if (DFS(i + 1, k)) return true;
            change.pop_back();
            change.push_back({ i,1 });
            if (DFS(i + 1, k)) return true;
            change.pop_back();
    }
    return false;
}
 
 
 
int main(int argc, char** argv) {
    int test_case, answer;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        // 입력받기
        cin >> D >> W >> K;
        memset(film, 0, sizeof(film));
        for (int i = 0; i < D; i++) {
            for (int j = 0; j < W; j++) {
                cin >> film[i][j];
            }
        }
        memcpy(film_copy, film, sizeof(film_copy));
 
        // 검사하기
        answer = K;
        for (int k = 0; k < K; k++) {
            change.clear();
            if (DFS(0,k)) {
                answer = k;
                break;
            }
        }
 
        cout << "#" << test_case << " " << answer << "\n";
    }
    return 0;
}

실행 결과

실행 결과 : Pass (1,101ms)