[SWEA] 2112. 보호필름

2112. 보호 필름

SW Expert Academy

 

• 다른 사람 풀이

#세로 r=d, 가로 c=w
# 특성 a =0,b=1 합격기준 k
# 약품 투입횟수 최솟값
#투입하지 않고 통과가능 -> 0

#성능검사
def check(graph): #graph가 바뀌기 때문에 graph를 받아서 검사해야함
    for i in range(c):
        cnt = 1
        for j in range(1,r): #범위 주의
            if graph[j][i]==graph[j-1][i]:
                cnt+=1
            else:
                cnt=1
            if cnt>=k: break; #이 코드가 없으면 오답 (넘어가면 retrun False문을 실행하지 않아야하므로)
        if cnt<k:
            return False
    return True


def dfs(depth, idx, pick): #현재 선택 수, 탐색위치, 선택횟수 기준
    global result
    if depth>=result: return

    if depth==pick:
        if check(graph):
            result=min(result,depth)
        return #if문 상관없이 무조건 리턴

    for i in range(idx, r):
        for d in range(2): #약품 a,b둘 중 하나
            graph[i]= drug[d]
            dfs(depth+1, i+1, pick)
            graph[i]=basic[i] #기존값으로 복원



T= int(input())

for tc in range(1,T+1):
    r,c,k=map(int,input().split())

    graph=[]
    for _ in range(r):
        graph.append(list(map(int,input().split())))

    basic=[g[:] for g in graph] #복원할때 사용할 기존 배열
    drug=[[0]*c, [1]*c] #교체해서 보낼 배열

    if check(graph): #약품없이 통과하면 0
        result=0
        #exit()하면 나머지 테케가 안돌아버리기 때문에 쓰면 안됨
    else:
        result=int(1e9)
        for j in range(1,r+1):
            dfs(0, 0, j) #1~r개 약물 선택하는 경우 모두 돌리는 것

    print(f'#{tc} {result}')