[Algorithm] 16987. 계란으로 계란치기

16987: 계란으로 계란치기(백트래킹)

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

• 문제 티어 : G5
• 풀이 여부 : Failed → Solved
• 소요 시간 : 38:41

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
eggs = [list(map(int, input().rstrip().split())) for _ in range(N)]

def backtrack(curr, broken):
  if curr == N: # 모든 계란으로 계란치기를 한 경우(N번째 계란까지 온 경우 -> curr:2 -> curr+1로 보내므로)
    global max_broken
    max_broken = max(max_broken, broken)
    return max_broken
  
  if eggs[curr][0] <= 0 or broken == N-1: # 현재 계란이 깨지거나(eggs[curr][0] : 내구도 < 0), 더이상 깨질 수 있는 계란이 없는 경우
    backtrack(curr+1, broken) # 정답 도출 조건(curr == N)을 위한 재귀

  else:
    for i in range(N): # 현재 들고있는 계란 기준 본인 제외, 왼/오 칠 수 있으므로
      if i != curr and eggs[i][0] > 0: # 깨지지 않은 다른 계란이 있는 경우
        eggs[i][0] -= eggs[curr][1] # curr 계란으로 상대 계란(i) 침
        eggs[curr][0] -= eggs[i][1] # 상대 계란(i)로 curr 계란 침

        # curr과 i번째 계란이 깨졌는지 확인 후 broken으로 넘김
        backtrack(curr+1, broken + (eggs[curr][0] <= 0) + (eggs[i][0] <= 0)) # 다음 계란으로 재귀 호출

        # 내구도 복원 -> 다른 경로 탐색에 영향을 주지 않기 위해
        eggs[i][0] += eggs[curr][1] # backtrack에 넘겼으므로 내구도 복원
        eggs[curr][0] += eggs[i][1] # backtrack에 넘겼으므로 내구도 복원

    # 모든 계란이 깨짐 OR 현재 계란(curr)만 남은 경우 
    if not any(eggs[i][0] > 0 for i in range(N) if i != curr): # 칠 수 있는 다른 계란이 없는 경우
      backtrack(curr+1, broken) # 다음 계란으로 넘어감

max_broken = 0
backtrack(0, 0)
print(max_broken)

접근 방식

처음에는 슬라이딩 윈도우 또는 투포인터를 사용해서 구현해야 하는 문제인가 했지만,
문제 상에서 현재 들고있는 계란 기준 왼/오 방향 상관없이 가장 많은 계란을 깰 수 있는 방법을 찾아야 하는 것이기에
완전탐색 중 백트래킹을 사용해서 가능한 경우의 수들만을 살펴보는 알고리즘을 사용해 풀이했다.

유의해야 할 점은,
N번의 순회를 할 때, 다음 조건을 backtrack 함수의 인자로 넣어 재귀호출을 한 다음, 복원해줘야 하는 점이다.

배운점 및 느낀점

이 문제는 5번은 더 풀어봐야겠다….^^