[백트랙킹]백준16987번 계란으로 계란치기

백준16987 계란으로 계란치기

보통 dfs를 사용한 풀이가 많은 것 같은데, 나는 백트랙킹을 이용해 풀었다.

계란끼리 부딫히는 과정이 조금 복잡하게 느껴질 수는 있지만 함수로 따로 구현한다면 복잡하지 않게 백트랙킹을 구현할 수 있다.

void fight(int idx1, int idx2){
    
    arr[idx1].first -= arr[idx2].second;
    arr[idx2].first -= arr[idx1].second;
    if(arr[idx1].first <= 0){
        isBroken[idx1] = true;
        brokenCount++;
    }
    if(arr[idx2].first <= 0){
        isBroken[idx2] = true;
        brokenCount++;
    }
}

fight 함수는 계란끼리 부딫히는 과정을 구현한다. 매개변수로는 인덱스 두 개를 받고, 각 인덱스에 해당하는 계란끼리 부딫힌다. 각 계란의 내구도에서 상대 계란의 무게를 빼준다. 만약 계란의 내구도가 0 이하가 되면 계란이 깨진 것으로 표시하고, 계란을 깬 횟수를 증가시킨다.

void unFight(int idx1, int idx2){
    bool flag1 = false;
    bool flag2 = false;
    if(isBroken[idx1]){
        flag1 = true;
    }
    if(isBroken[idx2]){
        flag2 = true;
    }
    arr[idx1].first += arr[idx2].second;
    arr[idx2].first += arr[idx1].second;
    if(arr[idx1].first > 0){
        isBroken[idx1] = false;
        if(flag1)brokenCount--;
    }
    if(arr[idx2].first > 0){
        isBroken[idx2] = false;
        if(flag2)brokenCount--;
    }
}

unFight 함수는 계란끼리 부딫혔던 것을 다시 복구한다. 중요한 건 , 계란이 깨졌었는지 여부를 확인하고 계란을 깬 횟수를 다시 감소시켜야 한다. 계란이 원래 깨져있었고 복구한 계란의 내구도가 0보다 크다면 계란을 깬 횟수를 다시 빼줘야 한다.

나머지 과정은 문제에서 요구하는 조건을 그대로 옮겨주면 된다.

void btk(int cur){
    //만약에 가장 최근에 들었던 계란 (cur)이 맨 오른쪽일 경우 종료
    if(cur == N){
        if(brokenCount > answer) answer = brokenCount;
        return;
    }
    bool flag = false;
    for(int i=0;i<N;i++){
        if(i!=cur && !isBroken[cur] && !isBroken[i]){
            flag = true;
            fight(cur, i);
            btk(cur+1);
            unFight(cur, i);
        }
    }
    if(!flag) btk(cur+1);

}

문제에서 주어진 조건은 다음과 같다.

1. 가장 왼쪽의 계란을 골라야 한다. ⇒ 백트랙킹을 처음 시작할 때 매개변수로 0 을 주면 0번째 계란, 즉 가장 왼쪽에 있는 계란을 고르게 된다.
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 하나를 친다.

⇒ 백트랙킹 함수 내에서 반복문을 돌면서 깨지지 않은 계란을 찾는다.

a. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.

if(i!=cur && !isBroken[cur] && !isBroken[i])

백트랙킹 함수 내에서는 반복문이 0부터 시작하기 때문에 i ≠ cur 이라는 조건을 넣어줘야 한다. 만약 그렇지 않으면 손에 들고 있는 계란으로 손에 들고 있는 계란을 치는 상황이 발생하게 된다. 그리고, 손에 든 계란이 깨졌는지 깨지지 않았는지, 치려는 계란이 이미 깨져있는지 깨져있지 않은지 확인한다.

만약 위의 조건을 만족하면

if(i!=cur && !isBroken[cur] && !isBroken[i]){
            flag = true;
            fight(cur, i);
            btk(cur+1);
            unFight(cur, i);
        }

다음 과정을 진행한다.

계란을 부딫히고(fight), 다음 계란(cur+1)으로 넘어간다.

백트랙킹 함수를 탈출하면 다시 복구한다. (unFight)

여기서 flag를 true로 바꾸는 것은 현재 깨지지 않은 계란, 즉 부딫힐 수 있는 계란이 아직 남아있다는 뜻이다.

만약 어떤 계란도 조건을 만족하지 못한다면 flag는 false인 채로 반복문을 탈출하게 된다.

그 경우에는

btk(cur+1) 

을 수행해 아무 것도 하지 않고 다음 계란으로 넘어간다.

단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

if(cur == N){
        if(brokenCount > answer) answer = brokenCount;
        return;
    }

이 과정을 그대로 거치면 최대로 계란을 깰 수 있는 횟수를 구할 수 있다.

#include <iostream>

using namespace std;

int N;
pair<int,int> arr[9];
int brokenCount = 0;
int answer = 0;
bool isBroken[9];
void fight(int idx1, int idx2){
    
    arr[idx1].first -= arr[idx2].second;
    arr[idx2].first -= arr[idx1].second;
    if(arr[idx1].first <= 0){
        isBroken[idx1] = true;
        brokenCount++;
    }
    if(arr[idx2].first <= 0){
        isBroken[idx2] = true;
        brokenCount++;
    }
}
void unFight(int idx1, int idx2){
    bool flag1 = false;
    bool flag2 = false;
    if(isBroken[idx1]){
        flag1 = true;
    }
    if(isBroken[idx2]){
        flag2 = true;
    }
    arr[idx1].first += arr[idx2].second;
    arr[idx2].first += arr[idx1].second;
    if(arr[idx1].first > 0){
        isBroken[idx1] = false;
        if(flag1)brokenCount--;
    }
    if(arr[idx2].first > 0){
        isBroken[idx2] = false;
        if(flag2)brokenCount--;
    }
}
int checkEggs(int cur){
    for(int i=0;i<N;i++){
        if(i!=cur){
            if(!isBroken[i]) return i;
        }
    }
    return -1;
}
void btk(int cur){
    //만약에 가장 최근에 들었던 계란 (cur)이 맨 오른쪽일 경우 종료
    if(cur == N){
        if(brokenCount > answer) answer = brokenCount;
        return;
    }
    bool flag = false;
    for(int i=0;i<N;i++){
        if(i!=cur && !isBroken[cur] && !isBroken[i]){
            flag = true;
            fight(cur, i);
            btk(cur+1);
            unFight(cur, i);
        }
    }
    if(!flag) btk(cur+1);
}

int main(){
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> arr[i].first;
        cin >> arr[i].second;
    }
    
    //제일 왼쪽에 있는거 픽
    btk(0);
    cout << answer;
}