[SWEA] 보호 필름 (모의 SW 역량테스트) / python

1. 문제 설명

보호 필름은 엷은 투명한 막을 D장 쌓아서 제작된다.
막은 동일한 크기를 가진 바(bar) 모양의 셀들이 가로 방향으로 W개 붙여서 만들어진다.
이렇게 제작된 필름은 두께 D, 가로 크기 W의 보호 필름이라고 한다.

 

각 셀들은 특성 A 또는 특성 B를 가지고 있다.
보호 필름의 성능은 셀들의 특성이 어떻게 배치됨에 따라 결정된다.
보호 필름의 성능을 검사하기 위해 합격기준 K라는 값을 사용한다.
충격은 보호 필름 단면의 세로 방향으로 가해지므로, 세로 방향 셀들의 특성이 중요하다.

 

단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.

 

약품은 막 별로 투입할 수 있으며 이 경우 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다.
특정 막에 약품 A를 투입하면 막 내의 모든 셀들이 특성 A로 변경되며, 약품 B를 넣게 되면 특성이 모두 특성 B로 변경된다.

두께 D, 가로크기 W인 보호 필름 단면의 정보와 합격기준 K가 주어졌을 때, 약품 투입 횟수를 최소로 하여 성능검사를 통과할 수 있는 방법을 찾고, 이때의 약품 투입 횟수를 출력하라.
약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.

 

2. 풀이 전 계획과 생각

입력

• D → 보호 필름의 두께
• W → 보호 필름의 가로 크기
• K → 합격 기준
• grid → 보호 필름 단면의 정보 (2차원 배열) (0 : 특성 A, 1 : 특성 B)

 

구하고자 하는바

성능 검사를 통과할 수 있는 약품의 최소 투입 횟수

 

중요한 조건

• 각 셀들은 특성 A 또는 특성 B를 가지고 있다.
• 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.
• 약품은 막 별로 투입할 수 있으며 이 경우 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다.

 

패턴, 규칙성 파악하기

1. 성능 검사를 통과하는지 확인한다.
2. 통과하지 못한다면, 1~D번째 막에 A의 약품 투입, B의 약품을 투입하고 다시 확인한다.
   🤔 그렇다면, 투입을 어떻게 할 것인가?
   약품 투입을 최소로 해야하므로, 약품을 1번 투입하고 확인하고 … D번까지 투입하고 확인해주자.
   1번 투입할 때, A 투입하고 확인하고 B 투입하고 확인해주자.
   

 

전체 설계

1. 성능 검사를 통과하는지 확인한다.
2. 통과하지 않으면,
   • 막을 1개 ~ D개 선택하며 아래를 반복한다.
     1. 막의 개수를 선택하면 그때 combination을 구한다.
     2. 통과하면 종료하고 갯수를 리턴한다.

def check():

def combination(idx, count):

def simulate():
    if check():
        return 0
    else:
        for count in range(1, D + 1):
            combination(0, count):
            if answer < 14:
				return count

for test_case in range(1, int(input()) + 1):
    D, W, K = map(int, input().split())
    film = [ list(map(int, input().split())) for _ in range(D) ]

 

필요한 로직

• 성능검사를 통과하는지 확인하는 함수 모든 세로 방향에 대해서 동일한 특성의 셀들이 K개 이상 있는지 확인한다.
• 약품을 막별로 투입하는 함수

 

풀이하면서 막혔던 점과 고민

약품을 막별로 투입할 때 2번 이상의 투입에서 투입할 때,
A 투입하고 B 투입할 때 경우를 어떻게 나눠서 투입할지 고민이 되었다.

⇒ 각 선택한 층마다 A 넣어보고, B 넣어보고 탐색하면 된다.

• 먼저 갯수만큼 막을 선택한다.
• 약품 선택해 투입한다. A를 투입하고 재귀 탐색 후, B를 투입한다.

 

함수 구체적으로

• 성능 검사를 통과하는지 확인하는 함수 모든 세로 방향에 대해서 동일한 특성의 셀들이 K개 이상 있는지 확인
  • 한 열의 동일한 셀이 K미만이면 즉시 False 리턴한다.
  • 전체 반복문을 다 통과하면 True를 리턴한다.

def check():
    for c in range(W):
        count = 1
        for r in range(D - 1):
            if film[r][c] == film[r + 1][c]:
                count += 1
            else:
                count = 1
            # 동일 특성이 K개 이상이면 break 하고 다음 열 검사
            if count >= K:
                break
        # 해당 열에서 동일 특성이 K 미만이면 불합격
        if count < K:
            return False
    # 해당 열에서 동일 특성이 K 미만이면 불합격
    return True

• 약품을 막별로 투입하는 함수
  • 종료조건 막을 count 만큼 선택했을 때, 체크해주자. 통과하면 갱신한다.

def combination(idx, pick, selected):
    global answer

    if len(selected) == pick:
        if check():
            answer = min(pick, answer)
        return

    if idx == D + 1:
        return

    combination(idx + 1, pick, selected + [idx])
    combination(idx + 1, pick, selected)

def simulate():
    global answer

    if check():
        answer = 0
    else:
        for pick in range(1, D + 1):
            combination(0, pick, [])

            if answer < 14:
                break

for test_case in range(1, int(input()) + 1):
    answer = 14
    D, W, K = map(int, input().split())
    film = [list(map(int, input().split())) for _ in range(D)]
    
    simulate()
    print(answer)

 

3. 풀이하면서 막혔던 점과 고민

약품을 막별로 투입하는 함수

투입할 막부분에서 선택만 했지, 선택하고
약품을 투입하는 경우의 수를 백트레킹으로 어떻게 처리해야 할지 감이 잡히지 않았다.

⇒ 백트레킹할 때 경우의 수를 나눠보자. 경우에 따라 어떻게 처리할지 정의해보자.

 

가지치기 조건

• 주입 횟수가 최소 약품 주입 횟수보다 크거나 같으면 가지치기한다.

 

종료 조건

• pick 횟수에 도달했다면 검사 후 갱신한다.
• 약물을 투입할 막이 D를 넘어서면 종료한다.

 

가는 경우

• 약물을 투입하지 않는 경우
• A약물을 투입하는 경우
• B약물을 투입하는 경우

def inject(idx, count, pick):
    global answer
    # 최소 약품 주입 횟수보다 크거나 같으면 가지치기
    if count >= answer:
        return

    # pick 횟수에 도달했다면 검사 후 갱신
    if count == pick:
        if check():
            answer = min(answer, pick)
        return
		
		# 약물을 투입할 막의 index가 D를 넘어서면 종료
		if idx >= D:
			return

    temp = film[idx]
    inject(idx + 1, count, pick)
    
    film[idx] = [0] * W
    inject(idx + 1, count + 1, pick)
    
    film[idx] = [1] * W
    inject(idx + 1, count + 1, pick)
    
    film[idx] = temp

 

4. 풀이

def check():
    for c in range(W):
        count = 1
        for r in range(D - 1):
            if film[r][c] == film[r + 1][c]:
                count += 1
            else:
                count = 1
            # 동일 특성이 K개 이상이면 break 하고 다음 열 검사
            if count >= K:
                break
        # 해당 열에서 동일 특성이 K 미만이면 불합격
        if count < K:
            return False
    # 해당 열에서 동일 특성이 K 미만이면 불합격
    return True

def inject(idx, count, pick):
    global answer
    # 최소 약품 주입 횟수보다 크거나 같으면 가지치기
    if count >= answer:
        return

    # pick 횟수에 도달했다면 검사 후 갱신
    if count == pick:
        if check():
            answer = min(answer, pick)
        return
		
		# 약물을 투입할 막의 index가 D를 넘어서면 종료
    if idx >= D:
        return

    temp = film[idx]
    # 약물을 투약하지 않는 경우
    inject(idx + 1, count, pick)
    
    # A 약물을 투약하는 경우
    film[idx] = [0] * W
    inject(idx + 1, count + 1, pick)
    
    # B 약물을 투약하는 경우
    film[idx] = [1] * W
    inject(idx + 1, count + 1, pick)

    film[idx] = temp

def simulate():
    global answer

    if check():
        answer = 0
    else:
        for pick in range(1, D + 1):
            inject(0, 0, pick)

            if answer < 14:
                break

for test_case in range(1, int(input()) + 1):
    answer = 14
    D, W, K = map(int, input().split())
    film = [list(map(int, input().split())) for _ in range(D)]

    simulate()
    print(f'#{test_case} {answer}')

 

5. 풀이 후 알게 된 개념과 소감

• 최대 / 최솟값 갱신 여부로 불가능한지, 가능한지의 여부를 정의할 수 있다.
• 가지치기 해서 갈 수 있는 경우를 먼저 정의해주고 그에 따라 표시하고 다음으로 가면, 모든 경우를 다 따져줄 수 있다.
  
  보통 백트레킹 문제를 풀 때, 무조건적으로 경우를 다 선택하고 난 뒤에
  다 선택한 경우를 한꺼번에 처리해주려고 했다.
  ⇒ 이 경우 문제가 복잡해지면 처리가 한꺼번에 하기 불가능한 경우도 있었다.
  
  이 접근 외에도 갈 수 있는 경우를 다 따져주고 그에 따라 표시하고 다음으로 가고
  종료되었을 때 처리해주면 복잡한 문제여도 쉽게 문제를 해결해줄 수 있다.
  ⇒ 그러므로, 문제가 복잡할수록 차근차근 갈 수 있는 경우를 찾고 그에 따라 처리해주자.