[SWEA] 2112. 보호 필름

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

SW Expert Academy

재귀를 이용한 조합으로 풀었다. 해당 행을 모두 0으로 바꾸고 재귀를 타고 들어가거나, 1로 바꾸고 재귀를 타고 들어가거나 원상 복귀 시키고(아무것도 하지 않고) 다음 행으로 넘어가는 식으로 풀면 된다.

 

처음에는 원상복귀 시키고 또 재귀를 타고 들어갔는데, 굳이 그렇게 해주지 않아도 for 문을 돌기 때문에 원상복귀한 상태 (아무것도 하지 않은 상태)로 다음 행으로 넘어간다. 이는 상태 트리를 그려보면 간단하게 알 수 있다.

각 solve 함수를 호출하자마자 k_check()로 체크해주기 때문에 모든 행 조합을 확인 할 수 있으며, cnt가 0 즉, 아무 약품도 바르지 않아도 되는 경우(맨 처음 호출된 solve)를 미리 체크해줄 수 있다.

def k_check(): # K개 연속 체크 함수
    for j in range(W):
        first_char = film[0][j]
        check = 0
        for i in range(D):
            if first_char == film[i][j]:
                check += 1
            else:
                first_char = film[i][j]
                check = 1
            if check >= K: # 한 열에 연속한 특성이 K보다 크면 더 볼 것 없음
                break
        if check < K: # 한 열에 연속한 특성이 K개보다 작으면 더 볼 것도 없음
            return False
    return True


def solve(cnt, change_idx): # 재귀를 이용한 조합
    global min_cnt

    if k_check(): # 함수 실행하자마자 연속 K개가 있는지 체크 (약품을 안 발라줘도 될 경우를 위한 가지치기)
        min_cnt = min(cnt, min_cnt)
        return

    if cnt >= min_cnt: # 가지치기
        return

    for i in range(change_idx+1, D):
        origin_film = film[i][:]
        for j in range(W): # 특성 변경
            film[i][j] = 1
        solve(cnt+1, i)

        for j in range(W): # 특성 변경
            film[i][j] = 0
        solve(cnt+1, i)

        for j in range(W): # 원상 복귀
            film[i][j] = origin_film[j]


for tc in range(1, int(input())+1):
    D, W, K = map(int, input().split())
    film = [list(map(int, input().split())) for _ in range(D)]
    min_cnt = D+1
    solve(0, -1)
    print('#{} {}'.format(tc, min_cnt))