[Problem Solving] 백준 16987 계란으로 계란치기

계란으로 계란치기 문제에 대한 자세한 설명은 다음 링크를 참고해주시기 바랍니다. 문제 설명

16987번: 계란으로 계란치기

계란으로 계란치기 문제는 브루트포스 알고리즘, 백트래킹 유형의 문제로 dfs 알고리즘을 사용하여 구현해야 합니다.

 

깨지지 않은 왼쪽 계란을 순서대로 들어 깨지지 않고, 들고 있지 않은 계란에 한 해 1회 부딪칠 수 있습니다. 모든 계란에 대한 처리가 끝났을 때 반복한 후에 깰 수 있는 계란의 최댓값을 결과로 출력합니다.

 

모든 경우에 대해서 처리하기 전까지는 어떤 경우가 계란을 최대로 많이 깰 수 있을지 알 수 없기 때문에 위의 과정을 모든 경우에 대해서 처리를 해줘야 합니다.

 

문제 해결 순서는 다음과 같습니다.

1. 왼쪽에 있는 계란을 든다.
2. 왼쪽 계란이 깨졌다면 다음 계란을 든다.
3. 왼쪽 계란이 깨지지 않았다면 부딪칠 수 있는 계란들을 부딪치고, 다음 계란을 든다.
4. 3의 과정에서 한 번도 계란을 부딪치지 않았다면 모든 계란이 깨져있다는 것이므로 dfs 알고리즘을 빠져나온다.
5. 1의 과정을 반복한다.

위의 해결 순서를 기반으로 작성한 코드입니다.

 

import sys
input = sys.stdin.readline

def check(eggs):
  count = 0
  for egg in eggs:
    if egg[0] <= 0:
      count += 1
  return count

def dfs(index, eggs):
  global answer

  if index == n:
    answer = max(answer, check(eggs))
    return 

  if eggs[index][0] <= 0:
    # 현재 계란의 내구도가 다 달았을 때 다음 계란으로 넘어간다.
    dfs(index + 1, eggs)
  else:
    # 현재 계란의 내구도가 남아있을 때 다른 계란들과 부딪친다. (현재 계란 제외, 내구도가 없는 계란 제외)
    is_all_broken = True
    for i in range(len(eggs)):
      if index != i and eggs[i][0] > 0:
        is_all_broken = False
        eggs[index][0] -= eggs[i][-1]
        eggs[i][0] -= eggs[index][-1]
        dfs(index + 1, eggs)
        eggs[index][0] += eggs[i][-1]
        eggs[i][0] += eggs[index][-1]
    # 모든 계란이 깨져있는 경우 dfs를 바로 빠져나와준다.
    if is_all_broken:
      dfs(n, eggs)

n = int(input())
eggs = []
answer = 0
for _ in range(n):
  eggs.append(list(map(int, input().split())))

dfs(0, eggs)
print(answer)

 

백트래킹 문제 유형은 많이 접해보지 못해서 해결하는데 오랜 시간이 걸렸습니다. 백트래킹의 경우 index의 값을 어떻게 넘기는지에 따라 조합, 순열 등 결과에 영향을 많이 받습니다.

 

따라서 백트래킹 문제는 문제의 조건을 잘 살펴보고 index의 값을 효율적으로 넘길 수 있는 방법에 대해서 고민해본 후에 문제 해결에 집중해야 할 것 같습니다.