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

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

SW Expert Academy

모의 SW 역량테스트 문제 중에 가장 고생한 문제인 것 같다. 시간 초과가 계속 나서 푸는데 1주일 정도 걸렸던 것 같다. 

처음에 bfs로 풀려고 시도했지만 안되서 bfs에 백 트레킹 기법을 사용하였다.

해결한 코드는 아래와 같다.

from copy import deepcopy


def check(k, d, w):
    for i in range(w):
        sub = 1
        for j in range(d - 1):
            if sub == k:
                break
            elif map1[j][i] == map1[j + 1][i]:
                sub += 1
            else:
                sub = 1
        if sub != k:
            return False
    return True


def solution(idx, count):
    global answer
    if count > answer:
        return
    if idx == d:
        if check(k, d, w):
            answer = count
        return
    else:
        solution(idx + 1, count)
        for y in range(w):
            map1[idx][y] = 1
        solution(idx + 1, count + 1)
        for y in range(w):
            map1[idx][y] = 0
        solution(idx + 1, count + 1)
        for y in range(w):
            map1[idx][y] = map2[idx][y]


t = int(input())
for test in range(1, t + 1):
    d, w, k = map(int, input().split())
    map1 = [list(map(int, input().split())) for _ in range(d)]
    map2 = deepcopy(map1)
    answer = k
    solution(0, 0)
    print('#{} {}'.format(test, answer))