[백준] 17136 색종이 붙이기 - 브루트포스(Brute-Force) + 백트래킹(BackTracking) JAVA

passionfruit200 2023. 8. 23. 10:09

2023. 8. 23. 10:09

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

17136번: 색종이 붙이기

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크

www.acmicpc.net

코드설명

브루트포스(Brute-Force) + 백트래킹(BackTracking) 문제입니다.

문제에서 유의해야할점은,

색종이를 붙일때는 길이가 11부터 종이를 넘어갔다고 판단해야합니다.

 public static boolean checkArr(int x, int y, int length) {
    boolean successFlag = true;
    if( x + length > 10 || y + length > 10 ) {
        return false;
    }
 
    for(int i=x; i < x + length;i++) {
        for(int j=y; j < y + length; j++) {
            if( arr[i][j] == 0) {
                successFlag = false;
                return false;
            }
        }
    }
 
    return successFlag;
}

예시로 들어보면, (0,5)에서 5번째 종이를 붙이면 (0, 10)이므로 10으로써 종이를 나간다고 판단한다면 5x5 종이를 붙일 수 없습니다.

2. 만약 arr[nowX][nowY] 가 1이 아니어서 색종이를 붙이지 않는경우에는 다음칸으로 넘어가기 위해 else처리하여 다음칸으로 넘어가야합니다

 if(arr[nowX][nowY] == 1) {
    for(int k=5;k>=1;k--) {
        //5x5, 4x4 내림차순으로 검사해야합니다.
        if( checkArr(nowX, nowY, k) == true) {
            if(usedPaper[k] > 0) {
                usedPaper[k] -= 1;
                checkPaperArr(nowX, nowY, k);
                simulate(nowX, nowY + k);
                erasePaperArr(nowX, nowY, k);
                usedPaper[k] += 1;
            }
 
        }    			
    }
}
else {
    simulate(nowX, nowY + 1);
}

arr[nowX][nowY] != 1 을 의미하는 else 문 로직을 추가하지 않는다면, 1이 없는경우 진전하지 않아 연산이 진행되지 않습니다.

3. 5x5, 4x4, 3x3 의 내림차순으로 색종이를 붙이지 않고도 1x1 -> 2x2 이런형식으로 붙여도 됩니다.

색종이의 길이가 긴것부터 처리해야만 최소의 색종이로 붙일 수 있을거라고 생각하였는데 이번 문제 같은경우 완전탐색문제로써 어떤 색종이를 먼저 처리하든 결국은 모든 색종이를 처리하므로 상관이 없습니다.

이번 문제같은경우 2580 스도쿠 문제와 유사하다고 느꼈습니다.

코드

가장 빠른 속도의 코드입니다.

이 코드같은경우, 먼저 map에서 주어진 1의 개수를 구하고, 1을 색칠할떄마다 개수를 재귀함수에 추가하여, 모든 숫자를 다 색칠했다면 바로 종료되게 만들었습니다.

또한, 이전에는 Map 전체를 재귀함수 종료시 다시 원상복구에 사용했는데 간단하게 생각해보면, 어처피 색종이를 붙이려면 색종이가 붙는 칸이 모두 1이어야 하므로, 그 색종이의 SIZE만큼만 모두 1로 원상복구 시키면 됩니다.

또한 색종이를 붙인 이후에 해당 칸의 Col 값에 색종이의 SIZE만큼 바로 이동시켜주어 불필요 연산을 줄여주었습니다.

 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M, D;
	public static int answer = Integer.MAX_VALUE, oneCnt = 0;
	public static int[][] map = new int[10][10];
	public static boolean[][] coloredMap = new boolean[10][10];
	public static int[] colorPaper = new int[] { 5, 5, 5, 5, 5 };
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		for(int i=0;i<10;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<10;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
					oneCnt += 1;
				}
			}
		}
		
		simulate(0, 0, 0, 0, 0);
		if(answer == Integer.MAX_VALUE) {
			answer = -1; 
		}
		System.out.println(answer);
		
	}
	
	public static void simulate(int level, int r, int c, int colored, int used) {
		if(oneCnt == colored) {
			answer = Math.min(answer, used);
			return ;
		}
		if(c >= 10) {
			r = r + 1;
			c = 0;
		}
		if(r >= 10) {
			
			return ;
		}
		
		if(map[r][c] == 1) {
			
			//해당 map[r][c]에서 SIZE를 구합니다.
			for(int kind=0; kind < 5; kind++) {
				//kind만큼의 길이로 색종이를 구할 것 입니다.
				boolean colorableFlag = true;
				int coloredCnt = 0;	
				//만약 해당 색종이를 모두 다 썼다면 애초에 불가능합니다.
				if(colorPaper[kind] <= 0) continue;
				//만약 SIZE가 넘칠경우 애초에 불가능합니다.
				//r도 포함이므로 범위는 r + kind 입니다.
				if(r + kind < 0 || r + kind >= 10 || c + kind < 0 || c + kind >= 10) continue;
				
				//해당 칸에서 1x1, 2x2, 3x3, 4x4, 5x5 로 색칠할 수 있는지 확인할 것 입니다.
				for(int i=0; i<kind + 1; i++) {
					for(int j=0; j<kind + 1; j++) {
						if(map[r+i][c+j] == 0) {
							colorableFlag = false;
						}
					}
				}
				
				//만약 해당 Size의 종이로 색칠할 수 있다면,
				if(colorableFlag == true) {
					colorPaper[kind] -= 1;
					for(int i=0; i<kind + 1; i++) {
						for(int j=0; j<kind + 1; j++) {
							coloredCnt += 1;
							map[r+i][c+j] = 0;
						}
					}
					simulate(level + 1, r, c + kind + 1, colored + coloredCnt, used + 1);		
					for(int i=0; i<kind + 1; i++) {
						for(int j=0; j<kind + 1; j++) {
							map[r+i][c+j] = 1;
						}
					}
					colorPaper[kind] += 1;
				}
			}
		}
		else if(map[r][c] == 0){
			simulate(level + 1, r, c + 1, colored, used);
		}
		
	}
}

함수적으로 풀어본 코드

 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[][] arr;
	public static int[][] visited;
	public static int[] usedPaper;
	public static int answer = Integer.MAX_VALUE;
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
 
    	arr = new int[10][10];
    	visited = new int[10][10];
    	usedPaper = new int[6];
    	for(int i=0;i<10;i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		for(int j=0;j<10;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	for(int i=1;i<6;i++) {
    		usedPaper[i] = 5;
    	}
    	
    	simulate(0, 0);
    	
    	if(answer == Integer.MAX_VALUE) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);	
    	}
    	
    }
    
    public static void simulate(int nowX, int nowY) {
    	
    	boolean endFlag = true;
    	for(int i=0;i<10;i++) {
    		for(int j=0;j<10;j++) {
    			if(arr[i][j] == 1) {
    				endFlag = false;
    				break;
    			}
    		}
    	}
    	
    	if(endFlag == true) {
    		int answerCnt = 0;
    		for(int i=1;i<6;i++) {
    			answerCnt += 5 - usedPaper[i]; 
    		}
    		answer = Math.min(answer, answerCnt);
    		
    		return ;
    	}
    	if(nowX >= 9 && nowY >= 10)
    		return ;
    	
    	if(nowY >= 10) {
    		nowX += 1;
    		nowY = 0;
    	}
    	
    	if(arr[nowX][nowY] == 1) {
    		for(int k=5;k>=1;k--) {
        		//5x5, 4x4 내림차순으로 검사해야합니다. ( 완전탐색이기에 오름차순으로 해도 상관없습니다. )
        		if( checkArr(nowX, nowY, k) == true) {
        			if(usedPaper[k] > 0) {
        				usedPaper[k] -= 1;
        				checkPaperArr(nowX, nowY, k);
        				simulate(nowX, nowY + k);
        				erasePaperArr(nowX, nowY, k);
        				usedPaper[k] += 1;
        			}
        			
        		}    			
    		}
    	}
    	else {
    		simulate(nowX, nowY + 1);
    	}
    	
    	
    	
    }
    
    public static boolean checkArr(int x, int y, int length) {
    	boolean successFlag = true;
    	if( x + length > 10 || y + length > 10 ) {
    		return false;
    	}
    	
    	for(int i=x; i < x + length;i++) {
    		for(int j=y; j < y + length; j++) {
    			if( arr[i][j] == 0) {
    				successFlag = false;
    				return false;
    			}
    		}
    	}
    	
		return successFlag;
    }
    
    public static void checkPaperArr(int x, int y, int length) {
    	for(int i=x; i < x + length;i++) {
    		for(int j=y; j < y + length; j++) {
				arr[i][j] = 0;
    		}
    	}    		    	
    }
    
    public static void erasePaperArr(int x, int y, int length) {
    	for(int i=x; i < x + length;i++) {
    		for(int j=y; j < y + length; j++) {
				arr[i][j] = 1;
    		}
    	}    		    	
    }
    
    
}

불필요하게 시간이 오래걸리는 코드입니다.

시간이 오래걸리는 이유는, 완전탐색(Brute-Force) 과정에서 전체 Map을 모두 돌면서 이전 Level의 Map으로 되돌립니다, 어처피 색칠을 할경우 1인 부분만 색칠을 하므로 색종이를 붙였다면, 그 색종이 안의 공간은 모두 1 로 다시 되돌리면 됩니다.

 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M, D;
	public static int answer = Integer.MAX_VALUE, oneCnt = 0;
	public static int[][] map = new int[10][10];
	public static boolean[][] coloredMap = new boolean[10][10];
	public static int[] colorPaper = new int[] { 5, 5, 5, 5, 5 };
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		for(int i=0;i<10;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<10;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
					oneCnt += 1;
				}
			}
		}
		
		simulate(0, 0, 0, 0, 0);
		if(answer == Integer.MAX_VALUE) {
			answer = -1; 
		}
		System.out.println(answer);
		
	}
	
	public static void simulate(int level, int r, int c, int colored, int used) {
		if(oneCnt == colored) {
			answer = Math.min(answer, used);
			return ;
		}
		if(c >= 10) {
			r = r + 1;
			c = 0;
		}
		if(r >= 10) {
			
			return ;
		}
		
		int[][] storeMap = new int[10][10];
		for(int i=0;i<10;i++) {
			for(int j=0;j<10;j++) {
				storeMap[i][j] = map[i][j];
			}
		}
		
		if(map[r][c] == 1) {
			
			//해당 map[r][c]에서 SIZE를 구합니다.
			for(int kind=0; kind < 5; kind++) {
				//kind만큼의 길이로 색종이를 구할 것 입니다.
				boolean colorableFlag = true;
				int coloredCnt = 0;	
				//만약 해당 색종이를 모두 다 썼다면 애초에 불가능합니다.
				if(colorPaper[kind] <= 0) continue;
				//만약 SIZE가 넘칠경우 애초에 불가능합니다.
				//r도 포함이므로 범위는 r + kind 입니다.
				if(r + kind < 0 || r + kind >= 10 || c + kind < 0 || c + kind >= 10) continue;
				
				//해당 칸에서 1x1, 2x2, 3x3, 4x4, 5x5 로 색칠할 수 있는지 확인할 것 입니다.
				for(int i=0; i<kind + 1; i++) {
					for(int j=0; j<kind + 1; j++) {
						if(map[r+i][c+j] == 0) {
							colorableFlag = false;
						}
					}
				}
				
				//만약 해당 Size의 종이로 색칠할 수 있다면,
				if(colorableFlag == true) {
					colorPaper[kind] -= 1;
					for(int i=0; i<kind + 1; i++) {
						for(int j=0; j<kind + 1; j++) {
							if(map[r+i][c+j] == 1) {
								coloredCnt += 1;
								map[r+i][c+j] = 0;
							}
						}
					}
					simulate(level + 1, r, c + kind + 1, colored + coloredCnt, used + 1);		
					for(int i=0;i<10;i++) {
						for(int j=0;j<10;j++) {
							map[i][j] = storeMap[i][j];
						}
					}
					colorPaper[kind] += 1;
				}
			}
		}
		else if(map[r][c] == 0){
			simulate(level + 1, r, c + 1, colored, used);
		}
		
	}
}

처음에 문제에서 0이 적힌 칸에 색종이가 있으면 안된다라는 조건을 읽지않고, 풀었습니다.

가장 큰 최소한의 종이를 구하기 위해 덮을 수 있는 가장큰 종이로 덮어서 진행했습니다.

이렇게 풀경우 따로 색종이를 붙였다는 Boolean[][] 배열을 사용해서 색종이가 붙였는지 안붙여있는지 확인할 수 있습니다.

이 과정에서 실수했던점은, kind는 0 으로 시작하여 해당 값도 포함입니다.

하지만, 처음에는 r + kind +1 로 처리하여 색종이의 길이가 1개 더 길어지는 오류가 있었습니다.

아래와 같이 수정했습니다.

if(r + kind < 0 || r + kind >= 10 || c + kind < 0 || c + kind >= 10) continue;

 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
 
답 : 4
 
 
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
 
답 : 2
적절한 답은 5 이지만 색종이가 0 에도 놓일 수 있는 상태에서 최소값은 2입니다.

 package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M, D;
	public static int answer = Integer.MAX_VALUE, oneCnt = 0;
	public static int[][] map = new int[10][10];
	public static boolean[][] coloredMap = new boolean[10][10];
	public static int[] colorPaper = new int[] { 5, 5, 5, 5, 5 };
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		for(int i=0;i<10;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<10;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
					oneCnt += 1;
				}
			}
		}
		System.out.println(oneCnt);
		simulate(0, 0, 0, 0, 0);
		System.out.println(answer);
		
	}
	
	public static void simulate(int level, int r, int c, int colored, int used) {
//		System.out.println("Colored:"+colored);
		if(oneCnt == colored) {
			answer = Math.min(answer, used);
			return ;
		}
		if(c >= 10) {
			r = r + 1;
			c = 0;
		}
		if(r >= 10) {
			
			return ;
		}
		
		boolean[][] storeColoredMap = new boolean[10][10];
		int[][] storeMap = new int[10][10];
		for(int i=0;i<10;i++) {
			for(int j=0;j<10;j++) {
				storeColoredMap[i][j] = coloredMap[i][j];
				storeMap[i][j] = map[i][j];
			}
		}
		
		if(map[r][c] == 1) {
			
			for(int kind = 0; kind < 5; kind ++) {
				boolean coloredSuccessFlag = true;
				if(r + kind < 0 || r + kind >= 10 || c + kind < 0 || c + kind >= 10) continue;
				if(colorPaper[kind] > 0) {
					for(int i=0; i<kind + 1; i++) {
						for(int j=0; j<kind + 1; j++) {
							//만약 이미 색칠된 것이 하나라도 존재한다면, 실패입니다. 
							if(coloredMap[r+i][c+j] == true) {
								coloredSuccessFlag = false;
							}
						}
					}
					
					if(coloredSuccessFlag == true) {
						int coloredCnt = 0;
						colorPaper[kind] -= 1;
						for(int i=0; i<kind + 1; i++) {
							for(int j=0; j<kind + 1; j++) {
								coloredMap[r+i][c+j] = true;
								if(map[r+i][c+j] == 1) {
									map[r+i][c+j] = 0;
									coloredCnt += 1;
								}
							}
						}
						
						simulate(level + 1, r, c + kind, colored + coloredCnt, used + 1);
						
						for(int i=0;i<10;i++) {
							for(int j=0;j<10;j++) {
								coloredMap[i][j] = storeColoredMap[i][j];
								map[i][j] = storeMap[i][j];
							}
						}
						colorPaper[kind] += 1;
					}
					
				}
			}
		}
		
		else if(map[r][c] == 0){
			simulate(level + 1, r, c + 1, colored, used);
		}
		
		
		
	}
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 2669 직사각형 네개의 합집합의 면적 구하기 - 구현 JAVA (0)	2023.08.24
[백준] 1759 암호 만들기 - 백트래킹 + Stream JAVA (0)	2023.08.23
[백준] 2661 좋은수열 - 백트래킹(Backtracking) + 문자열(String) + 아이디어(Idea) JAVA (0)	2023.08.22
[백준] 1062 가르침 - 백트래킹(BackTracking) + 조합(Combination) JAVA (0)	2023.08.22
[백준] 2580 스도쿠 - 백트래킹(Backtracking) + DFS(깊이우선탐색) JAVA (0)	2023.08.21

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

passionfruit200