백준 17136번 : 색종이 붙이기[java]

1. (0,0)부터 (9,9)까지 탐색을 진행합니다.

 

2. 탐색중 "1"을 만나면 사용가능한 가장 큰 색종이를 사용합니다.

 

- 사용 가능한 색종이가 없는 경우

- (9,9)에 도달한 경우

- 현재 사용한 색종이의 수가 최솟값보다 커진 경우

▶ 이 3가지 경우에는 직전의 "1"로 돌아가 이전에 붙였던 색종이를 때고 한 단계 작은 색종이를 붙이고 탐색을 재개합니다.

 

3. (9,9)에 도달한 경우에는 사용한  색종이의 최솟값을 갱신합니다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main{
	static int[][] map = new int[10][10];
	static int[][] original_Map = new int[10][10];
    static int min = Integer.MAX_VALUE;
    static int[] paper = {0,0,0,0,0};
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean zero = true;
        // map도입부
        for(int y=0; y<10; y++) {
        	String[] str = br.readLine().split(" ");
        	for(int x=0; x<10; x++) {
        		map[y][x] = Integer.parseInt(str[x]);
        		original_Map[y][x] = map[y][x];
        		if(map[y][x] == 1) zero = false;
        	}
        }
        Search(0,0);
        
        if(zero) {
        	System.out.print(0);
        }
        else if(min == Integer.MAX_VALUE){
        	System.out.print(-1);
        }
        else {
        	System.out.print(min);
        }
    }
    
    // 현재 사용한 색종이의 갯수를 세는 함수
    public static int count() {
    	int papers = 0;
		for(int i=0; i<5; i++) {
			papers += paper[i];
		}
		return papers;
    }
    
    //x,y부터 탐색을 시작함
    public static void Search(int x, int y) {	
    	if(map[y][x] == 0) {
        	if(x==9 && y==9) {
    			int papers = count();
    			min = Math.min(papers, min);
    			return;
    		}
    		else {
    			if(count() >= min) return; 
    			next(x,y);
    		}
        }
    	
    	else { // map[y][x] == 1
    		if(count() >= min) return; 
    		for(int n=4; n>=0; n--) {
    			if(x+n >=10 || y+n >=10) {
    				continue;
    			}
    			if(paper[n]<5 && checkPaper(x, y, n)) {
    				//checkdraw();
    				paper[n] += 1;
    				next(x,y);
    				paper[n] -= 1;
    				uncheckPaper(x, y, n);
    			}
    		}
    	}
    }
    
    // 다음 1의 위치를 찾은 후 그 위치부터 탐색(Search)하는 함수
    public static void next(int x,int y) {
		int nextX = 9;
		int nextY = 9;
		boolean f = false;
		for(int Y=y; Y<=9; Y++) {
			for(int X=0; X<=9; X++) {
				if(map[Y][X] == 1) {
					nextX = X;
					nextY = Y;
					f = true;
					break;
				}
			}
			if(f) break;
		}
		Search(nextX,nextY);
    }
    
    // x,y에 n크기의 색종이를 붙일 수 있는지 검사 + 붙일 수 있으면 붙이고 해당 부분을 0으로 바꾼다.
    public static boolean checkPaper(int x, int y, int n) {
    	for(int Y=y; Y<=y+n; Y++) {
    		for(int X=x; X<=x+n; X++) {
    			if(map[Y][X] == 0) {
    				return false;
    			}
    		}
    	}
    	for(int Y=y; Y<=y+n; Y++) {
    		for(int X=x; X<=x+n; X++) {
    			map[Y][X] = 0;
    		}
    	}
    	return true;
    }
    
    // 백트래킹에 사용, check과정에서 0으로 만들 부분을 1로 복구한다.
    public static void uncheckPaper(int x, int y, int n) {
    	for(int Y=y; Y<=y+n; Y++) {
    		for(int X=x; X<=x+n; X++) {
    			if(original_Map[Y][X] == 1) {
    				map[Y][X] = 1;
    			}
    			else {
    				map[Y][X] = 0;
    			}
    		}
    	}
    	//uncheckdraw();
    }
    /*
    // 디버깅용
    public static void checkdraw() {
    	System.out.print("Check\n");
    	for(int y=0; y<10; y++) {
    		for(int x=0; x<10; x++) {
    			System.out.print(map[y][x] + " ");
    		}
    		System.out.print("\n");
    	}
    	
    	System.out.print("\n");
    	System.out.print("\n");
    }
    
    public static void uncheckdraw() {
    	System.out.print("unCheck\n");
    	for(int y=0; y<10; y++) {
    		for(int x=0; x<10; x++) {
    			System.out.print(map[y][x] + " ");
    		}
    		System.out.print("\n");
    	}
    	
    	System.out.print("\n");
    	System.out.print("\n");
    }
    */
}