[백준] 17136번 색종이 붙이기 - JAVA

 

 

 

✍️풀이방식 

 

 

1. 문제 분석 

1이 있는 칸에만 색종이를 붙여야 하고 칸에 딱 맞게 붙여야 하는 것. 각 종류의 색종이를 5개씩 가지고 있기 때문에 한 종류 마다 5개까지 사용할 수 있다. 즉 전체 색종이 개수는 25개이다. 

 

색종이를 붙일수 있는 경우의 수를 백트래킹 알고리즘을 이용하여 구하면 된다. 지금까지 연습했던 문제들 중에 가장 난이도가 높은 문제였던 것 같다... 

 

 

2. 풀이 과정 

 

 

1. 색종이를 붙일 수 있는 1번째 위치를 찾는다.

 

2. 탐색 위치는 왼쪽 위에서 시작하여 오른쪽으로 이동하고, 오른쪽 끝에 도달하면 한 줄 아래로내려가서 다시 왼쪽부터 이동하는 방식으로 진행한다.  (가지치기를 극대화 하기 위해서 큰 색종이부터 탐색한다)  

 

3. 현재 선택한 위치에 가지고 있는 색종이를 붙일 수 있는지 확인한다. 붙일 수 있다면 탐색을 계속 진행하고 붙일 수 없다면 탐색을 종료한다. 현재까지 사용한 색종이 수가 이미 구한 최솟값을 초과하면 탐색을 중단한다. 

 

4. 모든 1을 덮는 탐색을 완료 하면 색종이 수를 기록한다. 기록된 색종이 수 중에서 가장 작은 값을 찾아 출력한다. 

 

5.색종이로 1을 덮는 과정을 해당 영역의 데이터를 0으로 변경하는 것으로 처리한다. 색종이가 중복되는 경우를 방지하기 위해서 

 

 

 

수도 코드 

backtracking(){
	    
	    if(색종이로 1이 적힌 모든 칸에 붙이고 x,y 좌표를 끝까지 탐색한 경우){
	        최소 사용 개수 업데이트 및 함수 반환 // 정답 도출 
	        
	        if(최소로 사용한 색종이 수보다 현재 탐색에서 사용한 색종이 수가 많으면)
	         함수 반환// 가지치기 
	            
	            

	        
	        if(현재 위치가 1이면){
	            크기가 큰 순서부터 색종이 5종류 중 재고가 있는 색종이 붙여보기 
	            
	            if(붙일 수 있으면){// 가지치기 
	            해당 크기 색종이 재고 1감소 
	            종이 붙이기 -> 종이 덮이는 부분을 1에서 0으로 변경 
	            현재 사용한 색종이 수를 1증가 시키고 다음위치로 좌표 이동하여 backtracking 함수 재귀 호출 
	            해당 크기 색종이 재고 1 증가 
                종이 떼어내기-> 기존에 덮인 부분 0에서 다시 1로 변경 
	
	            }
	        
	        }
	       
	    } else{
	        다음 위치로 좌표 이동하여 backtracking 함수 재귀 호출 
	    }
	}

 

 

 

 

 

---

 

 

 

🖥️문제풀이

 

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

public class Main{
    
    static int[][] M = new int[10][10];         // 종이 상태 저장 배열
    static int[] S = {0,5,5,5,5,5};             // 남은 색종이 수 저장 배열
    static int result = Integer.MAX_VALUE;   // 최소 사용 개수 저장 
    
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		for(int i=0; i<10; i++){
		    StringTokenizer st = new StringTokenizer(br.readLine());
		    for(int j=0; j<10; j++){
		        M[i][j] = Integer.parseInt(st.nextToken()); //종이 상태 입력 받기 
		    }
		}
		
		 backtracking(0,0); //좌표, 몇개 색종이 썼는지 
		
		 if (result ==Integer.MAX_VALUE){
		     System.out.println(-1); 
		 }else{
		     System.out.println(result); 
		 }
	
		
	}
	
	public static void backtracking(int xy, int useCnt){
        //정답처리
        
        if(xy==100){
            result = Math.min(result, useCnt);//사용한 개수를 업데이트 해준다 
            return; 
            
        }
	    int x = xy%10; 
	    int y = xy/10; 
	    
	    if(result<=useCnt)return; 
	    
	    if(M[y][x]==1){//현재 위치가 1이라면 
	    
	        for(int i=5; i>0;i--){
	             if(S[i]>0 && check(x,y,i)){
	                S[i]--; 
	                fill(x,y,i,0);
	                backtracking(xy+1, useCnt+1);// 사용한 개수 증가 후 다음좌표로 이동, 백트래킹킹
	                fill(x,y,i,1);
	                S[i]++;
	             
	             }
	        }
	        
	    }else{
	        backtracking(xy+1, useCnt); // 다음 좌표로 이동 후 백트래킹 
	    }
	   
	    
	    
	}
	
	public static void fill(int x, int y, int size,int num){
	    for(int i=y;i<y+size;i++){
	        for(int j=x; j<x+size;j++){
	            M[i][j] = num; 
	        }
	    }//색종이 사이즈에 맞게 숫자 넣기 
	   
	    
	}//색종이 붙였다가 떼는 과정 
	
	
	public static boolean check(int x, int y, int size){
	    
	    if(x+size>10||y+size>10)return false; //사이즈가 10이 넘어가면 바로 종료 
	    
	    for(int i=y;i<y+size;i++){
	        for(int j=x; j<x+size;j++){
	           if(M[i][j] != 1) return false; //1이 아니면 붙일 수 없음 
	        }
	    }
	    return true; //붙일 수 있음 
	    
	}//색종이를 사용했을 때 다 1이 들어가는 지확인 


}