SW Expert Academy - 보호 필름 (python)

❓ 문제 - SW Expert Academy 보호 필름 python 풀이법

 

출처 

(https://swexpertacademy.com/main/solvingProblem/solvingProblem.do)

SW Expert Academy

 

 

 

📝 문제해결법

1. 이 문제는 완전탐색으로 풀었다.

• DFS를 통해 약품처리를 하는 행을 선택하면서 check() 함수를 통해 성능검사를 통과하는지 검사하고 성공하면 약품처리한 횟수와 min_answer 비교해서 최솟값을 갱신하고, 실패하면 DFS로 약품처리를 하는 흐름으로 코드를 작성하였다.
• DFS를 리턴하는 조건으로 우선 약품처리를 하는데 현재 최소 약품처리 횟수보다 더 크게 약품처리를 했다면 리턴한다.(시간 절약)
• 또한 약품처리를 하는데 만약 행의 갯수만큼 약품처리를 했다면 check() 함수로 성능검사를 통과하는 지 검사해서 최솟값 횟수를 갱신한다.
• check() 함수를 통해 현재 성능검사가 통과되는지 확인하는데, 한 열에 대해 일단 k값과 같은 갯수를 확인하고 같다면 break 해서 다음 열에 대해 확인하고,  한 행이 밑에 행과 같다면 same +1 해주고, 다르다면 same을 1로 초기화한다. 한 열에 대해 same 카운트 후, k값과 same 값이 다르다면 False를 리턴한다.
• 현재 행에서는 약품처리 하지 않고, 다음 행에 대해 DFS를 들어간다.
• 현재 행에서는 약품처리(A특성)한 후, DFS 들어간다.
• 현재 행에서는 약품처리(B특성)한 후, DFS 들어간다.
• 위 약품처리 후 다시 보드 상태를 돌리기 위해 원래 board정보로 행 정보를 초기화한다.

 

2. 문제 풀면서 느낀점

• 처음에 dfs를 통해 모든 경우를 탐색했지만 시간초과가 나서 다른 사람 코드 참고해서 수정했다.
• 일단 탐색을 계속하면서 약품 처리 횟수가 현재 최소 약품처리 횟수보다 크다면 약품처리할 필요가 없으므로 리턴한다.(처음에 k 값보다 현재 약품처리 횟수가 크다면 리턴하게 해서 재귀 횟수가 너무 커짐...)
• 3중 for문으로 약품특성(0, 1), 행(약품처리 행 선택), 열(해당 행 약품처리)로 구현하고 한 행에 대해 약품처리 후 다시 dfs를 들어가도록 했으나.. 우선 약품처리를 위해 탐색하는 행을 +1 해주고 dfs 처리, A 특성으로 약품처리 후 dfs, B특성으로 약품처리 후 dfs하도록 변경하는 게 더 깔끔하다.
• 또한 다 약품처리한 후 다시 board값을 약품 처리 전 상태로 돌려놔야한다.

 

 

💻 소스코드

import copy
T = int(input())

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

def dfs(depth, idx, board2, k):
    global min_answer
    if depth > min_answer:
        return
    if idx == d:
        if check(board2, d, w, k):
            min_answer = depth
        return
    else:
        dfs(depth, idx+1, board2, k)
        for y in range(w):
            board2[idx][y] = 1
        dfs(depth+1, idx+1, board2, k)
        for y in range(w):
            board2[idx][y] = 0
        dfs(depth+1, idx+1, board2, k)
        for y in range(w):
            board2[idx][y] = board[idx][y]

for test_case in range(1, T+1):
    d, w, k = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(d)]
    board2 = copy.deepcopy(board)
    min_answer = k
    dfs(0, 0, board2, k)
    print(f'#{test_case} {min_answer}')