[백준] 16987 계란으로 계란치기 - 백트래킹 + DFS JAVA

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

16987번: 계란으로 계란치기

코드설명

백트래킹 + DFS 문제입니다.

문제로직입니다.

1. 각 계란의 깨는 순서에 따라 최대로 계란을 꺠는 갯수가 달라집니다. 그러므로, DFS로 모든 순서를 탐색하는 완전탐색을 진행합니다. 
   1. 만약 현재 깨려는 계란이 깨져있는경우, 아무것도 진행하지않고 다음 계란으로 넘어갑니다. 
   2. 만약 현재 꺠려는 계란이 안깨져있는경우, 다른 계란을 깨면서 simulate를 진행합니다.
2. 각 계란을 모두 돌지 않더라도 각 Simulate 마다 항상 깨진 계란의 개수를 갱신해줘야만 합니다. 그래야만, 모든 계란을 꺠지 않더라도 깨진 계란의 최대값을 얻을 수 있습니다.

 

문제에서 유의해야하는점은

• 각 계란을 깬뒤에 1 2 3 4 5 6 7 8 의 계란이 있으면 모든 계란을 한번씩 꺠진 처리한뒤에 처리하는것인줄알고서 헷갈렸는데 깨지지 않은 다른 계란 중에서 하나를 친다 ( 하나의 계란만 치고 넘어가면 됨 )
  • 위의 조건을 인지하지못해서 어떻게 풀어야하는지 고민을 했습니다.
• 문제에서 오류가 났던 부분은, 문제의 각 값들을 찍어보기 위하여 print 문을 했을때 무한 루프가 돌아서 오류인줄알았는데 출력문이 너무 많아서 발생한 경우입니다. 출력문이 계속해서 나온다면, 해당 출력문을 제거하고 출력해보시면 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N;
	public static int answer = 0;
	public static int[][] SiWi;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
 
    	SiWi = new int[N][2];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		SiWi[i][0] = Integer.parseInt(st.nextToken()); 
    		SiWi[i][1] = Integer.parseInt(st.nextToken());
    	}
    	
		simulate(0);
    	System.out.println(answer);
    }
    
    public static void simulate(int nowIdx) {
 
		int max = 0;
		for(int i=0;i<N;i++) { //최대의 꺠진 계란을 구하는것이므로 모든 simulate마다 먼저 실행해야합니다.
			if(SiWi[i][0] <= 0) { //만약 내구도가 0일시 계란이 꺠진것임으로 증가
				max += 1; 
			}
		}
		answer = Math.max(answer,  max);
    	
    	if(nowIdx == N) {
 
    		return ;
    	}
    	
    	
    	if(SiWi[nowIdx][0] > 0) {
	    	for(int i=0; i<N;i++) {
	    		if(i == nowIdx) continue;
	    		if(SiWi[i][0] <= 0) continue;
	    		
	    		SiWi[nowIdx][0] -= SiWi[i][1]; //기준계란의 내구도 감소
	    		SiWi[i][0] -= SiWi[nowIdx][1]; //오른쪽계란의 내구도 감소
	    		
	    		simulate(nowIdx + 1);
	    		
	    		SiWi[nowIdx][0] += SiWi[i][1]; //기준계란의 내구도 원상복구
	    		SiWi[i][0] += SiWi[nowIdx][1]; //오른쪽계란의 내구도 원상복구
	    	}
    	}else {
    		simulate(nowIdx + 1);
    	}
    	
    	
    	
    }
 
}