[백준/Python] 16987 - 계란으로 계란치기

문제 링크

https://www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

 

분류

- 브루트포스 알고리즘

- 백트래킹

 

코드

n = int(input())
origin_infos = [list(map(int, input().split())) for _ in range(n)]
ans = 0

def back(cnt, infos):
    global n, ans
    # 모든 계란을 던진 경우
    if cnt == n:
        broken_cnt = 0
        for info in infos:
            # 깨진 계란인 경우 집계
            if info[0] <= 0: broken_cnt += 1
        ans = max(ans, broken_cnt)
        return
    
    # cnt 번째 계란이 이미 깨진 경우 skip
    if infos[cnt][0] <= 0:
        back(cnt + 1, infos)
        return
    
    broken_cnt = 0
    for i in range(n):
        # 자기 자신을 깨트릴 순 없으므로 스킵
        if i == cnt: continue
        # i번째 계란이 깨진 경우 스킵
        if infos[i][0] <= 0: 
            broken_cnt += 1
            continue

        # cnt 번째 계란으로 i번째 계란을 깨트린다고 가정
        infos[i][0] -= infos[cnt][1]
        infos[cnt][0] -= infos[i][1]
        back(cnt + 1, infos)
        infos[i][0] += infos[cnt][1]
        infos[cnt][0] += infos[i][1]
    
    # 깨트릴 계란이 없는 경우 skip
    if broken_cnt == n - 1:
        back(cnt + 1, infos)

back(0, origin_infos)
print(ans)

 

문제 해결 방법

N(계란의 개수)가 최대 8개이기 때문에 백트래킹 기법을 사용하여 모든 경우의 수를 따져본다.

백트래킹 과정은 다음과 같다.

0. 백트래킹 함수가 호출된다는 것은 i번째 계란을 손에 든다는 것을 의미한다.
1. 만약 i번째 계란이 깨져있다면 다음 계란을 선택한다.(재귀)
2. i번째 계란으로 깨트릴 계란을 찾아 서로를 부딪힌다. 부딪히고 난 이후의 내구도 값을 기록하고 다음 계란을 선택한다.(재귀)
3. 만약 i번째 계란으로 깨트릴 계란을 찾지 못하여도 다음 계란을 선택한다.(재귀)
4. 모든 계란을 손에 들어봤다면(백트래킹 호출이 n번 이루어지면) 계란들의 내구도 값을 확인하여 정답을 갱신한다.

 

실수한 점

위와 같은 접근 방법으로 코드를 작성하기 이전에 다음과 같은 접근 방법으로 코드를 작성하였을 때 실수한 점이 있다.

1. eggs[i] = i번째 계란으로 깨트릴 계란의 숫자가 저장된 배열.
2. 백트래킹 기법을 활용해 가능한 모든 경우의 수를 eggs 배열에 담는다. (중복 순열)
3. eggs 배열이 모두 가득차면 eggs 배열을 순회하며 내구도의 변화를 시뮬레이션한다.

3번 과정에서 파이썬 라이브러리인 copy의 함수인 deepcopy 함수로 내구도를 담은 배열을 복사한 뒤, 내구도의 변화를 시뮬레이션 했다.

아마 말로 이해하는 것보다 코드로 이해하는 것이 직관적일 것 같다... 코드는 다음과 같은 흐름으로 작성했었다.

import copy
n = int(input())
origin_infos = [list(map(int, input().split())) for _ in range(n)]
ans = 0

def back(cnt, eggs):
    if cnt == n:
        # calc eggs
        infos = copy.deepcopy(origin_infos)
        # 깨진 계란 집계 후 answer 갱신
        broken_eggs = calc_with_eggs_array()
        ans = max(ans, broken_eggs)
        return
    for i in range(n):
        if i == cnt: continue
        eggs.append(i)
        back(cnt+1, eggs)
        eggs.pop()

우선, 위와 같이 코드를 작성하면 불가능한 경우도 모두 집계되기 때문에 틀린 정답을 출력한다.

또한, 깨진 계란을 확인하기 위해 copy.deepcopy 함수는 재귀적으로 내부의 값까지 모두 새로운 객체로 메모리에 복사하기 때문에 시간복잡도가 초과된다. 다음은 copy.deepcopy 함수의 소스 코드이다. 리스트를 대상으로 deepcopy를 수행했을 때 재귀적으로 모든 값이 복사됨을 확인할 수 있다.

def _deepcopy_list(x, memo, deepcopy=deepcopy):
    y = []
    memo[id(x)] = y
    append = y.append
    for a in x:
        append(deepcopy(a, memo))
    return y

 

 

느낀점

백트래킹 기법으로 문제를 풀 때, 문제가 제시하는 조건을 위배하는 경우를 집계해도 괜찮은지 다시 한 번 생각해보자!