[문제 풀이] 백준 16987번 계란으로 계란치기 JAVA

문제

  문제접근 방법   

해당 문제는 여러 개의 계란을 차례대로 들고 서로 부딪히며 가장 많은 계란을 깨는 상황을 찾는 문제로
각 계란은 내구도와 무게를 가지고 있으며, 한 계란으로 다른 계란을 치면 양쪽 계란의 내구도가 상대 계란의 무게만큼 줄어든다.
내구도가 0 이하가 되면 해당 계란은 깨진 것으로 처리되고 계란을 들고 있을 때 이미 깨졌거나 더 이상 칠 수 있는 계란이 없으면 그 차례는 그냥 넘어가야 한다. 최종적으로 모든 과정을 거쳤을 때 깨진 계란의 최대 개수를 출력하는 프로그램을 작성해야한다.

 

이 문제는 단순한 그리디나 규칙으로 풀 수 없기 때문에, 가능한 모든 경우를 탐색하는 완전 탐색 접근이 필요하다 생각했다.

그래서 먼저 계란을 차례대로 들고 아직 깨지지 않은 다른 계란과 부딪히게 하면서 내구도를 갱신하고, 그 결과 깨진 계란의 개수를 세어 나가는 식으러 설계하였다. 이후에는 원상복구를 해주며 다른 경우의 수를 탐색하는 백트래킹 방식으로 모든 시도를 진행하고 만약 현재 계란이 이미 깨졌거나 더 이상 칠 수 있는 계란이 없으면 그냥 넘어가고 다음 단계로 진행한다. 이렇게 모든 과정을 반복한 뒤 가능한 경우 중 가장 많은 계란이 깨지는 값을 최종 정답으로 선택하면 되는 것이다.

 

< 최종 코드 >

import java.io.*;
import java.util.*;

public class Main {
    static int N, ans;
    static int[] s, w;

    static void dfs(int idx, int broken) {
        if (idx == N) {
            ans = Math.max(ans, broken);
            return;
        }
        if (s[idx] <= 0 || broken == N - 1) {
            dfs(idx + 1, broken);
            return;
        }
        boolean hit = false;
        for (int j = 0; j < N; j++) {
            if (j == idx || s[j] <= 0) continue;
            hit = true;
            int bs = 0;
            s[idx] -= w[j];
            s[j] -= w[idx];
            if (s[idx] <= 0) bs++;
            if (s[j] <= 0) bs++;
            dfs(idx + 1, broken + bs);
            if (s[idx] <= 0) bs--;
            if (s[j] <= 0) bs--;
            s[idx] += w[j];
            s[j] += w[idx];
        }
        if (!hit) dfs(idx + 1, broken);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim());
        s = new int[N];
        w = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            s[i] = Integer.parseInt(st.nextToken());
            w[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0, 0);
        System.out.println(ans);
    }
}

 

이 문제의 코드는 DFS와 백트래킹을 기반으로 동작한다. 먼저 현재 인덱스의 계란을 손에 들고, 이미 깨졌거나 모든 계란이 거의 다 깨져 있다면 바로 다음 계란으로 넘어간다. 깨지지 않은 다른 계란을 찾으면 서로 부딪히게 하고, 내구도를 감소시키며 새로 깨진 계란 수를 계산한다.그 상태로 재귀 호출을 하여 다음 계란으로 넘어가며 탐색을 이어간다.
재귀가 끝나면 감소시킨 내구도를 원상복구하고 다른 경우의 수를 시도한다.
이 과정을 모든 계란에 대해 반복하여 최종적으로 가장 많이 깨진 계란 개수를 갱신한다. 

와 같은 식의 코드흐름을 가진다.