[SWEA] 2112. 보호필름(Python) / DFS

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

SW Expert Academy

# 1시간 1분 소요

많이 풀어본 유형이라 큰 고민 없이 풀어낸 문제다.

• 사용 알고리즘 : DFS 조합 
• 우선, 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다. 고 했으니, 성능검사 함수를 만들어줬다.(testPerformance())
  • 동일한 특성의 셀들이 K개 이상 연속으로 있는 경우에만 성능검사 통과
  • 한 열의 동일 셀이 K 미만이면  즉시 False 리턴
  • 이중 포문 통과하면 True 리턴하여 성능검사 통과 
• comb() 함수를 통해 DFS 재귀로 어떤 막을 몇개 선택할 것인지 조합 함수를 구현했다. 최소 1개에서 막의 갯수 D 개만큼 선택할 수 있도록 했다.
  • 이 때, result가 갱신됐다면 성능검사에 통과한 것이므로 break로 for문을 빠져나가고 result를 출력한다.
• comb() 조합 생성 함수 내에서
  • 맵 복원과 약품주입용으로 사용할 원본 배열을 저장해둔다.(raw, drugs)
  • 현재 depth가 갱신된 result보다 크거나 같다면 볼 필요 없으므로 가지치기
  •  depth가 뽑아야 할 갯수(pick)에 다다랐을 때, 성능검사 해주고 최솟값 갱신
  • 어떤 막을 선택할 것인지 select로 append(), pop() 해주며 관리
  • 약품 주입할 때는 미리 만들어준 drugs 이차원 배열로 0, 1 두 가지 경우에 대해 선택
  • 인덱스로 0과 1에 해당하는 약품을 주입한 후 꼭! 복원시켜줘야 한다.

 

파이썬 코드는 다음과 같다.

---

def testPerformance(A):			# 필름 성능 검사
    for c in range(W):
        cnt = 1
        for r in range(1, D):
            if A[r][c] == A[r-1][c]:
                cnt += 1
            else:
                cnt = 1
            if cnt >= K:        # 동일 특성이 K개 이상이면 break하고 다음 열 검사
                break
        if cnt < K:             # 해당 열에서 동일 특성이 K 미만이면 불합격
            return False
    return True                 # 모두 통과하면 합격

def comb(depth, k, pick):		# DFS 조합 구현
    global result
    if depth >= result:         # 최소 약품 주입 횟수보다 크거나 같으면 가지치기
        return
        
    if depth == pick:           # pick 횟수에 도달했다면 검사 후 갱신
        if testPerformance(film):
            result = min(result, depth)
        return
        
    for i in range(k, D):				# 막 선택
        for d in range(2):				# A 약품 or B 약품 둘 중 하나 선택
            select.append(i)
            film[i] = drugs[d]          # 약품 투입
            comb(depth+1, i+1, pick)
            film[i] = raw[i]            # 복원
            select.pop()

# main
T = int(input())
for tc in range(T):
    D, W, K = map(int, input().split())
    film = [list(map(int, input().split())) for _ in range(D)]
    raw = [f[:] for f in film]
    drugs = [[0] * W, [1] * W]

    if testPerformance(film):   # 원래의 필름으로 한 번에 성능 검사 통과
        result = 0
    else:                       # 한 번에 통과하지 못함 => 약물 투입
        result = float('inf')
        select = []
        for pick in range(1, D+1):
            comb(0, 0, pick)
            if result < float('inf'):   # 갱신된 적 있으면 break
                break

    print("#{} {}".format(tc+1, result))

---

• 시간 : 3078ms / 메모리 : 77468kb
• 고찰 : 3번째 푸는 문제인데 이번이 가장 빨리 푼 반면, 시간 / 공간복잡도가 많이 들었다.. 좀 더 효율적으로 짤 수 있도록 고민을 많이 하고 짜자! 재미있는 DFS 문제였다!