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 |