[백준] 16987 - 계란으로 계란치기 - 골드 5

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• 브루트포스 탐색, 백트래킹

---

1. 문제설명

문제가 긴데 요약하자면 다음과 같습니다.

인범이가 계란으로 계란을 치려고 합니다.

계란은 총 N개가 주어지며 각각의 계란은 내구도, 무게 가 존재합니다.

 

가장 왼쪽에 있는 계란을 우선 손으로 집고 나머지 계란중 하나를 오른손으로 집어서 계란끼리 부딪힙니다.

 

손에든 계란이 깨지든 깨지지않았든 현재 들고있는 계란을 내려놓고 다음 계란을 선택해 계란끼리 부딪힙니다.

 

만약 손에든 계란이 깨졋거나 더이상 깰수있는 계란이 없는 경우 계란을 치지 않고 넘어갑니다.

 

이때 인범이가 계란을 가장 많이 깰 수 있는 경우의 수를 구하는 문제입니다.

---

[제한사항]

• 시간 제한 2초
• 메모리 제한 512MB
• 1 ≤ N ≤ 8
• 내구도 Si(1 ≤ Si ≤ 300)와 무게 Wi(1 ≤ Wi ≤ 300)

---

2. 접근방식

 

우선 이번 문제는 백트래킹을 이용하여 구할 수 있는 모든 경우의 수를 구하는 문제입니다.

 

그렇다면 문제의 조건에 맞춰 하나씩 구현하면 되는 문제입니다.

 

문제의 조건을 순서대로 보겠습니다.

 

1. 가장 왼쪽에 있는 계란을 선택하고 왼손에 듭니다.

• 이건 DFS 탐색의 시작지점을 항상 0번 값으로 시작하면 되겠죠

2. 선택한 계란을 제외하고 나머지 계란 중 하나를 선택해 부딪힙니다.

• 이때 선택하는 조건은 현재 선택한 계란 이외의 계란을 선택해야 하니 전체 탐색을 실시할 때 이미 왼손에 든 계란은 아니어야 합니다.
• 또한 이미 깨진 계란이라면 선택할 이유가 없습니다.

이 두가지를 제외하고 나머지 계란을 선택하여 오른손에 듭니다.

 

3. 계란을 들었다면 계란끼리 부딪히고 넘어가기를 반복해 주어야 합니다.

• 계란은 내구도와 무게가 존재하고 왼손에 든 계란의 무게만큼 오른손 계란의 내구도가 감소하고
• 오른손에 든 계란의 무게만큼 왼손의 계란의 내구도가 감소합니다.
• 이때 부딪힌 계란중 깨진 계란이 있다면 계란이 깨진 횟수를 증가시켜 주고 다음 계란을 탐색해야겠죠
• 해당 순서의 백트래킹이 종료되었다면 조건을 초기화 하기 위해 계란이 부딪혔던 경우를 원래대로 돌려주어야 합니다.

 

4. 더이상 선택할 계란이 없는 경우 즉 왼손에 선택한 계란을 기준으로 오른손에 들 계란이 없는 경우 백트래킹을 종료해야겠죠

• 이때, 계란이 깨준 횟수를 선택해서 바꿔주어야 합니다. 이는 max를 이용해 현재 계란을 깬 횟수와 정답 중 더 큰 값으로 정답을 바꿔주고 백트래킹을 종료하면 됩니다.

위 조건들을 토대로 코드로 구현해 보겠습니다.

---

3. 코드

import sys
input = sys.stdin.readline

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

def DFS(n, count):
    global answer

    # 더 진행할 이유가 없는 경우 (가지치기)
    if answer >= (count + (N - n) * 2):
        return

    # 종료조건
    if n == N:
        answer = max(answer, count)
        return
    
    # 백트래킹 탐색 시작
    # 현재 선택한 계란이 깨진 계란인 경우
    if eggs[n][0] <= 0:
        DFS(n + 1, count)
    
    # 현재 선택한 계란이 깨지지 않은 경우 깨트릴 다른 계란 찾기
    else:
        flag = False
        for i in range(N):
            # 선택한 계란이 내 왼손에 있는 계란이거나, 이미 깨진 계란의 경우 넘어가기
            if i == n or eggs[i][0] <= 0:
                continue
            
            # 계란 깨기
            flag = True
            eggs[n][0] -= eggs[i][1]
            eggs[i][0] -= eggs[n][1]
            DFS(n + 1, count + int(eggs[n][0] <= 0) + int(eggs[i][0] <= 0))
            # 백트래킹 탐색 끝난 경우 계란 원래 대로 돌려놓기
            eggs[n][0] += eggs[i][1]
            eggs[i][0] += eggs[n][1]
        
        # 안깨진 계란을 선택하려는데 모든 계란이 깨져있는 경우
        if flag == False:
            DFS(n + 1, count)

answer = 0
DFS(0, 0)
print(answer)

---

[코드설명]

import sys
input = sys.stdin.readline

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

answer = 0
DFS(0, 0)
print(answer)

 

입력을 받고 받은 입력을 기준으로 DFS 백트래킹을 시작해 줄 겁니다.

 

계란은 N개 입력되는데 각각의 계란은 내구도, 무게 순서로 계란의 정보가 주어집니다.

 

DFS 탐색의 시작 위치는 항상 가장 왼쪽에 있는 계란이니 0번 계란을 선택해주고, 그 다음 0은 현재 계란을 부딪혀 계란이 깨진 횟수 입니다.

 

---

def DFS(n, count):
    global answer

    # 종료조건
    if n == N:
        answer = max(answer, count)
        return

 

DFS 탐색을 실시할 때 가장 먼저 종료조건을 생각해 주어야합니다.

 

현재 선택한 계란이 가장 마지막 계란이라면 더이상 선택할 계란이 없다는 뜻이니 여기서 종료 해줄겁니다.

 

이때 4번 조건을 만족하기 위해서 정답을 더 큰 값으로 바꿔주고 종료합니다.

 

그게 아니라면 백트래킹 탐색을 시작해 줄 겁니다.

---

# 백트래킹 탐색 시작
    # 현재 선택한 계란이 깨진 계란인 경우
    if eggs[n][0] <= 0:
        DFS(n + 1, count)
        
    # 현재 선택한 계란이 깨지지 않은 경우 깨트릴 다른 계란 찾기
    else:
        for i in range(N):
            # 선택한 계란이 내 왼손에 있는 계란이거나, 이미 깨진 계란의 경우 넘어가기
            if i == n or eggs[i][0] <= 0:
                continue
            
            # 계란 깨기
            eggs[n][0] -= eggs[i][1]
            eggs[i][0] -= eggs[n][1]
            DFS(n + 1, count + int(eggs[n][0] <= 0) + int(eggs[i][0] <= 0))
            # 백트래킹 탐색 끝난 경우 계란 원래 대로 돌려놓기
            eggs[n][0] += eggs[i][1]
            eggs[i][0] += eggs[n][1]

 

DFS 탐색을 실시하는데 현재 계란이 이미 깨진 계란인 경우가 있을 겁니다.

 

이전 백트래킹에서 계란끼리 부딪혀서 다음 계란을 선택하는 과정에

 

현재 계란이 안깨진 경우와

현재 계란이 깨진 경우가 존재하기 때문입니다.

 

이때 현재 계란이 깨졌다면 다음 계란을 선택해 주어야 합니다. 따라서 n을 증가시켜 주고 선택한 계란은 이미 깨진 계란이니 count 값은 증가시키지 않습니다.

 

현재 선택한 계란이 깨지지 않았다면 깨트릴 다른 계란을 찾아야 겠죠 이때 앞서 설정한 2번 조건이 필요합니다.

 

전체 탐색을 통해 깨트릴 계란을 찾는데 다음 계란이 현재 내 손에 있는 계란이거나 깨진 계란이라면 넘어가야 겠죠

 

이제 이 경우를 제외하면 계란을 깨트리고 백트래킹을 실시해 주어야 합니다.

 

계란이 깨지는 조건은 왼손의 계란의 무게를 기준으로 오른손의 계란의 내구도가 감소하고

오른손의 계란의 무게를 기준으로 왼손의 계란의 내구도가 감소합니다.

 

이때 왼손 혹은 오른손의 계란이 깨지거나 깨지지 않은 경우가 있을 수 있습니다.

 

둘다 깨진 경우 2가 증가하고 둘 중 하나만 깨진 경우는 1이 증가하겠죠 그 조건을 구분해 주기 위해 count에 더해줄 값으로 

eggs[n][0] <= 0 

eggs[i][0] <= 0 

즉 왼손과 오른손의 계란이 깨진 경우 True를 반환하니 1을 반환할 것이고 False 를 반환하면 0을 반환하니 값이 더해져도 의미가 없겠죠 이렇게 해서 다음 DFS 를 실시하는 겁니다.

 

이걸 풀어서 코드로 작성하면 이런 코드겠죠

    # 계란 깨기
        flag = True
        eggs[n][0] -= eggs[i][1]
        eggs[i][0] -= eggs[n][1]
        # 왼손의 계란만 깨진 경우
        if eggs[n][0] <= 0 and eggs[i][0] > 0:
            DFS(n + 1, count + 1)
            
        # 오른손의 계란만 깨진 경우
        elif eggs[i][0] <= 0 and eggs[n][0] > 0:
            DFS(n + 1, count + 1)
            
        # 둘다 깨진 경우
        elif eggs[n][0] <= 0 and eggs[i][0] <= 0:
            DFS(n + 1, count + 2)

        # 둘다 안 깨진 경우
        else:
            DFS(n + 1, count)

        # 백트래킹 탐색 끝난 경우 계란 원래 대로 돌려놓기
        eggs[n][0] += eggs[i][1]
        eggs[i][0] += eggs[n][1]

 

그걸 간단하게 해준게 저 위의 코드인 겁니다.

DFS 모든 조건을 int() + int() 로 바꿔 1, 1, 2, 0 의 경우의 수를 한 줄로 구한 겁니다.

 

여기서 DFS 백트래킹이 종료되면 계란을 원상복구 시켜 다음 탐색이 가능하도록 해줍니다.

---

# 현재 선택한 계란이 깨지지 않은 경우 깨트릴 다른 계란 찾기
    else:
    	# 추가된 부분
        flag = False
        for i in range(N):
            # 선택한 계란이 내 왼손에 있는 계란이거나, 이미 깨진 계란의 경우 넘어가기
            if i == n or eggs[i][0] <= 0:
                continue
            
            # 계란 깨기
            flag = True
            eggs[n][0] -= eggs[i][1]
            eggs[i][0] -= eggs[n][1]
            DFS(n + 1, count + int(eggs[n][0] <= 0) + int(eggs[i][0] <= 0))
            # 백트래킹 탐색 끝난 경우 계란 원래 대로 돌려놓기
            eggs[n][0] += eggs[i][1]
            eggs[i][0] += eggs[n][1]
        
        # 추가된 부분
        # 안깨진 계란을 선택하려는데 모든 계란이 깨져있는 경우
        if flag == False:
            DFS(n + 1, count)

 

모든 탐색을 실시하며 한가지 고려해야 할 조건이 있는데 왼손에 계란을 골랐는데 다음에 고를 계란이 없는 경우 입니다.

그러한 경우 왼손의 계란을 내려놓고 다음번 계란을 고르고 다시 계란을 골라야 하니 flag를 설정해 정상적인 실행이 가능하도록 해주었습니다.

---

def DFS(n, count):
    global answer

    # 더 진행할 이유가 없는 경우 (가지치기)
    if answer >= (count + (N - n) * 2):
        return

 

마지막으로 가지치기 즉 시간을 줄이는 작업을 진행해 주었습니다.

 

여기까지 작성해도 이미 결과는 출력되지만 혹여나 시간 초과가 발생할 수 있으니 탐색의 조건을 조금 수정해 주었습니다.

 

이러한 가지치기는 종료 조건보다 상단에 작성하는 경우가 대부분 입니다.

 

가지 치기의 경우 현재 answer 에 남은 계란이 모두 깨지는 경우를 더해도 answer 보다 작은 경우 더이상 탐색을 해봤자 유의미한 결과를 낼 수 없으니 일찍 종료하는 것 입니다.

 

물론 이러한 가지치기를 자세하게 하면 할수록 좋을수도 있지만 탐색의 시간이 길어져 오히려 시간이 늘어나는 경우도 있습니다.

---

4. 결과

 

메모리가 넉넉하여 python 에서 pypy3로 실행했습니다.

---

[회고]

 

이번 문제는 조건 파악이 굉장히 까다로웠습니다.

 

문제를 읽으며 이게 무슨 소리지,,, 이러한 생각을 많이 했었고 백트래킹을 잘 해결하는 편이 아니어서 까다로운 문제였습니다.

 

결정적으로 문제를 해결할 수 있었던 이유는 2번 조건을 이해하고 나서 였습니다.

 

손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.

 

이게 2번 조건인데

천천히 읽어보면 계란이 깨지든, 깨지지 않든, 무조건 다음번 계란을 탐색하여 부딪힌다는 겁니다.

즉, 모든 계란을 부딪혀서 결과를 찾을 건데, 만약 계란이 깨진다면 그때는 조건을 분기하면 된다는 뜻이었습니다.

 

이렇게 2번 조건을 이해하고 나니 차근차근 접근 방식을 세울 수 있었습니다.

 

또 마지막 설명에 덧 붙여둔 고려사항은 제가 생각한 방식이 아니었습니다.

 

질문 게시판을 통해 계란을 칠수 없는 경우를 생각할 수 있었습니다.

현재 왼손의 계란이 깨지지 않은 계란이어서 다음번 계란을 탐색해야 하는데 남은 계란을 선택할 수 없는 경우가 문제였던 겁니다.

 

따라서 계란끼리 부딪혀서 계란의 부딪힘 자체가 발생하면 flag를 True로 바꿔주는데

왼손 계란을 기준으로 모든 계란끼리 부딪힐 수 있나 없나를 비교했을 때 없다면 False로 두어 다음번 탐색을 강제한 겁니다.

 

또 가지치기의 경우 python으로 돌려보니 시간이 오래걸려서 시간을 줄이는 방법을 생각해 보았는데

어차피 메모리가 넉넉하니 pypy로 돌리는데 좀더 일찍 종료하는 조건은 없을까 생각하다가 찾게 되었습니다.

 

현재 계란을 기준으로 남은 계란의 수는 전체 계란의 수 - 현재 계란의 번호 입니다.

 

이러면 남은 계란의 수를 알 수 있고 count값이 증가할 때 왼손의 계란도 깨지고 오른손의 계란도 깨지는 경우 즉 모두 깨지는 경우 2가 증가합니다.

 

남은 계란이 전부 두개 씩 깨진다 해도 answer의 값을 바꿀수 없다면 더이상 탐색할 이유가 없던 것입니다.

 

그 결과 시간을 많이 줄였고 문제를 해결할 수 있었습니다.