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

시간 제한	메모리 제한
15 초	힙 정적 메모리: 256 MB / 스택 메모리 1MB

문제

성능이 우수한 보호 필름을 제작하려고 한다.

보호 필름은 엷은 투명한 막을 D장 쌓아서 제작된다.

막은 동일한 크기를 가진 바(bar) 모양의 셀들이 가로 방향으로 W개 붙여서 만들어진다.

이렇게 제작된 필름은 두께 D, 가로 크기 W의 보호 필름이라고 한다.

각 셀들은 특성 A 또는 특성 B를 가지고 있다. 보호 필름의 성능은 셀들의 특성이 어떻게 배치됨에 따라 결정된다.

보호 필름의 성능을 검사하기 위해 합격기준 K라는 값을 사용한다.

충격은 보호 필름 단면의 세로 방향으로 가해지므로, 세로 방향 셀들의 특성이 중요하다.

단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.

성능검사에 통과하기 위해서 약품을 사용하여야 한다.

약품은 막 별로 투입할 수 있으며 이 경우 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다.

특정 막에 약품 A를 투입하면 막 내의 모든 셀들이 특성 A로 변경되며, 약품 B를 넣게 되면 특성이 모두 특성 B로 변경된다.

두께 D, 가로크기 W인 보호 필름 단면의 정보와 합격기준 K가 주어졌을 때, 약품 투입 횟수를 최소로 하여 성능검사를 통과할 수 있는 방법을 찾고,

이때의 약품 투입 횟수를 출력하라.

약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.

제약사항

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 5초

2. 보호 필름의 두께 D는 3이상 13이하의 정수이다. (3≤D≤13)

3. 보호 필름의 가로크기 W는 1이상 20이하의 정수이다. (1≤W≤20)

4. 합격기준 K는 1이상 D이하의 정수이다. (1≤K≤D)

5. 셀이 가질 수 있는 특성은 A, B 두 개만 존재한다.

입력

첫 줄에 총 테스트 케이스의 개수 T가 주어진다.

두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다.

각 테스트 케이스의 첫 줄에는 보호 필름의 두께 D, 가로크기 W, 합격기준 K가 차례로 주어진다.

그 다음 D줄에 보호 필름 단면의 정보가 주어진다. 각 줄에는 셀들의 특성 W개가 주어진다. (특성A는 0, 특성B는 1로 표시된다.)

출력

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 성능검사를 통과할 수 있는 약품의 최소 투입 횟수이다. 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.

풀이

DFS를 통해 각 층 마다 약품 A 혹은 B를 투입하거나, 투입하지 않는 경우를 탐색했다.

그리고 각 탐색마다 테스트를 통과할 수 있는지 확인하여, 통과할 수 있다면 최소 주입 횟수를 갱신하고 탐색을 중단한다.

test_film()

보호 필름 테스트는 세로로 연속하는 특성을 찾아햐 한다.

def chk_test():
    chk_a_list = [0] * k
    chk_b_list = [1] * k

    for w_i in range(w):
        is_success = False

        for d_i in range(d - k + 1):
            cur_chk = [film[tmp_i][w_i] for tmp_i in range(d_i, d_i + k)]
            if cur_chk == chk_a_list or cur_chk == chk_b_list:
                is_success = True
                break
        if not is_success:
            return False
    return True

그래서 위와 같이 k만큼 세로로 배열을 만들어 같은 값으로 연속하는 지 확인한다. ([film[tmp_i][w_i] for tmp_i in range(d_i, d_i + k)])

코드

test_case = int(input())

def chk_test():
    chk_a_list = [0] * k
    chk_b_list = [1] * k

    for w_i in range(w):
        is_success = False

        for d_i in range(d - k + 1):
            cur_chk = [film[tmp_i][w_i] for tmp_i in range(d_i, d_i + k)]
            if cur_chk == chk_a_list or cur_chk == chk_b_list:
                is_success = True
                break
        if not is_success:
            return False
    return True


def test_film(film, depth=0, cnt_inject=0, chk_list=[]):
    global min_inject
    
    if cnt_inject >= min_inject:
        return

    if chk_test():
        min_inject = min(min_inject, cnt_inject)
        return

    if depth >= d:
        return
    
    origin_membrane = film[depth][:]

    # 현재 층을 그대로
    test_film(film, depth + 1, cnt_inject)

    # 현재 층을 a로
    film[depth] = inject_a
    test_film(film, depth + 1, cnt_inject + 1)
    film[depth] = origin_membrane

    # 현재 층을 b로
    film[depth] = inject_b
    test_film(film, depth + 1, cnt_inject + 1)
    film[depth] = origin_membrane

for t in range(test_case):
    d, w, k = map(int, input().split())

    film = [list(map(int, input().split())) for _ in range(d)]
    
    inject_a = [0] * w
    inject_b = [1] * w

    min_inject = float('inf')

    test_film(film)
    print(f"#{t + 1} {min_inject}")

DFS를 진행하면서 지금의 필름(film), 깊이(depth), 투입한 횟수(cnt_inject)를 넘겨준다. 이 때 약물을 투입했다면, 재귀가 끝난 후 원래 상태로 돌려준다.