백준 16987 : 계란으로 계란치기 (Python)

본문 링크

def BackTracking(start):

    global Answer
    if start==N:
        total=0
        for i in range(N):
            if egg[i][0]<=0:
                total+=1

        Answer=max(Answer,total)
        return

    if egg[start][0]<=0:
        BackTracking(start+1)
        return

    check=True
    for i in range(N):
        if i==start:
            continue
        if egg[i][0]>0:
            check=False
            break

    if check: #다 깨져있는 경우
        Answer=max(Answer , N-1) #자기빼고 전부다니깐 N-1
        return

    for i in range(N):
        if i==start or egg[i][0]<=0:
            continue
        egg[start][0]-=egg[i][1]
        egg[i][0]-=egg[start][1]
        BackTracking(start+1)
        egg[start][0]+=egg[i][1]
        egg[i][0]+=egg[start][1]


N=int(input())
egg=[ list(map(int,input().split())) for _ in range(N) ] #내구도와 무게
Answer=0
BackTracking(0)

print(Answer)
"""
가장 왼쪽의 계란을 든다.
손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 
단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.
이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
 
가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다.
단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.
"""

📌 어떻게 접근할 것인가?

백트래킹을 사용해 접근하였습니다.

종료조건이라던지 확인해야할 부분이 많이 있었는데 , 그런구부븐 그냥 if 문을 따로 써줘서 return 을 해주는게 복잡성을 줄일 수 있는 방법인것 같습니다.

if start == N:
    total = 0
    for i in range(N):
        if egg[i][0] <= 0:
            total += 1
	Answer=max(Answer,total)
	return

만약 마지막까지 도착했다면 지금까지 깨진 계란의 수를 저장합니다.

if egg[start][0] <= 0:
    BackTracking(start + 1)
    return

만약 지금들고있는 계란이 깨졌다면 start+1 로 이동하고 바로 return 합니다.

check = True
for i in range(N):
    if i == start:
        continue
    if egg[i][0] > 0:
        check = False
        break

if check:  # 다 깨져있는 경우
    Answer = max(Answer, N - 1)  # 자기빼고 전부다니깐 N-1
    return

계란이 다 깨져있는 경우입니다.
그럴떄는 자기빼고 전부다 깨져있으므로 $N-1$ 을 저장하고 바로 return 합니다

for i in range(N):
    if i == start or egg[i][0] <= 0:
        continue
    egg[start][0] -= egg[i][1]
    egg[i][0] -= egg[start][1]
    BackTracking(start + 1)
    egg[start][0] += egg[i][1]
    egg[i][0] += egg[start][1]

백트래킹 부분입니다. 자기자신을 깨지않고 , 깨려는 계란이 아직깨지지않았다면
계란을깨주고 재귀를 해줍니다. 백트래킹을 해야하기 때문에 재귀가 끝나고 나면 다시 원상태로 되돌려줍니다.

백트래킹에서 복잡한 조건을 다뤄야 할때 백트래킹을 하는 부분에 조건을 추가하는 것보다 함수 내에서 따로 조건을 추가해서 return 을 적절히 사용하는 것이 중요하다고 느꼈습니다.