백준 17136 색종이 붙이기(자바)

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

17136번: 색종이 붙이기

 

색종이를 칸에 맞게 가장 최적으로 붙이는 개수를 구해야 하는 문제.

1,2,3,4,5의 nxn사이즈를 가진 색종이가 5장씩 주어지는데

처음에 가장 큰 사이즈부터 완탐을 돌리고 테케는 다 맞았는데 돌려보니 17%인가 18%에서 나가떨어졌다.

 

최적을 구해야 하니 가장 큰 것부터 돌리는 게 아니라 백트래킹으로 접근해야 문제를 풀 수 있었다.

 

 

우선 전체 코드를 보자

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[][] map;
	static int[] papercount = {0,5,5,5,5,5};
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		map = new int[10][10];
		for(int i=0; i<10; i++) {
			for(int j=0; j<10; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		back(0,0,0);
		
		if(min==Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(min);			
		}
	}

	public static void back(int x, int y, int cnt) {
		// 종료
		// 너가 마지막까지 갔어?(x+1로 재귀를 타서 x==10이 마지막)
		if(x==10 && y==9) {
			min = Math.min(min, cnt);
			return;
		}
		
		// 이미 현재 cnt가 min을 초과했으면 할 필요 X
		if(min<=cnt) {
			return;
		}
		
		// x를 전부 다 봤어? 그러면 x는 0으로 초기화 하고
		// y+1을 해서 back에다 다시 넘겨(그러면 다음 줄을 보게 됨)
		if(x==10) {
			back(0, y+1, cnt);
			return;
		}
		
		
		// 재귀
		if(map[y][x]==1) {
			for(int i=1; i<=5; i++) {
				if(papercount[i]>0 && check(x,y,i)) { // 종이도 남아있고 붙일 자리도 있어?
					papercount[i]--; // 색종이 하나 빼버리고
					go(x,y,0,i); // 색종이 0으로 붙여
					back(x+1, y, cnt+1); // 다음 오른쪽 칸 검사해~
					go(x,y,1,i); // 색종이 1로 떼버려
					papercount[i]++; // 색종이 다시 더해
				}
			}
		}else { // 1이 아니면 다음 칸을 검색한다!
			back(x+1,y,cnt);
		}
	}
	
	// 색종이 붙였다가 떼는 메서드(x, y의 좌표, 무엇으로 붙일지, 사이즈의 크기)
	public static void go(int x, int y, int flag, int size) {
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				map[i+y][j+x] = flag;
			}
		}
	}
	
	// 색종이 붙일 수 있는지 자리 확인하는 메서드(x, y의 좌표, 사이즈의 크기)
	public static boolean check(int x, int y, int size) {
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				// 맵을 초과했어? false 돌려준다.
				if(y+i>9 || x+j>9) {
					return false;
				}
				// 범위에 1이 없어? false 돌려준다.
				if(map[y+i][x+j]!=1) {
					return false;
				}
			}
		}
		return true;
	}
}

 

이제 코드를 하나씩 살펴보겠다.

static int[][] map;
static int[] papercount = {0,5,5,5,5,5};
static int min = Integer.MAX_VALUE;

색종이를 받을 2차 map

종이의 개수를 카운트할 papercount (1번부터 5번 index만 사용하겠다는 소리, 0번은 버린다)

최소 개수를 파악할 min을 static으로 선언했다.

 

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	map = new int[10][10];
	for(int i=0; i<10; i++) {
		for(int j=0; j<10; j++) {
			map[i][j] = sc.nextInt();
		}
	}
	
	back(0,0,0);
	
	if(min==Integer.MAX_VALUE) {
		System.out.println(-1);
	}else {
		System.out.println(min);			
	}
}

우선 map에 종이를 입력받는다.

이후 백트래킹을 돌리는데 x좌표, y좌표, cnt 총 3개를 넘길 거다.

 

public static void back(int x, int y, int cnt) {
	// 종료
	// 너가 마지막까지 갔어?(x+1로 재귀를 타서 x==10이 마지막)
	if(x==10 && y==9) {
		min = Math.min(min, cnt);
		return;
	}
	
	// 이미 현재 cnt가 min을 초과했으면 할 필요 X
	if(min<=cnt) {
		return;
	}
	
	// x를 전부 다 봤어? 그러면 x는 0으로 초기화 하고
	// y+1을 해서 back에다 다시 넘겨(그러면 다음 줄을 보게 됨)
	if(x==10) {
		back(0, y+1, cnt);
		return;
	}

종료 조건으로 3가지의 조건을 두었다.

1. x==10 && y==9

밑에서 재귀를 돌릴 때 back(x+1, y, cnt)로 돌리게 설정했다.

그래서 x=10, y=9가 되는 순간 끝에 도달했다는 소리니 min와 cnt를 비교해서 min에 저장하고 return 한다.

 

2. min<=cnt

이 조건은 넣어도 되고 안 넣어도 된다. 단지 가지를 치기 위해 넣었다.

cnt가 이미 min을 넘어섰으면 더 볼 필요가 없다는 소리.

 

3. x==10

만약에 (0,0,0)으로 입력이 주어졌다고 생각하자.

밑에서 재귀를 (x+1, y, cnt)로 돌리니 (10, 0, cnt)가 되는 순간이 다가온다.

그러면 0번 행의 오른쪽은 전부 탐색했다는 소리니 x를 0으로 바꾸고 y+1을 해서 back을 다시 돌린다.

 

// 재귀
	if(map[y][x]==1) {
		for(int i=1; i<=5; i++) {
			if(papercount[i]>0 && check(x,y,i)) { // 종이도 남아있고 붙일 자리도 있어?
				papercount[i]--; // 색종이 하나 빼버리고
				go(x,y,0,i); // 색종이 0으로 붙여
				back(x+1, y, cnt+1); // 다음 오른쪽 칸 검사해~
				go(x,y,1,i); // 색종이 1로 떼버려
				papercount[i]++; // 색종이 다시 더해
			}
		}
	}else { // 1이 아니면 다음 칸을 검색한다!
		back(x+1,y,cnt);
	}
}

재귀 조건이다.

만약에 맵이 1이면 우선 색종이의 개수를 파악한다.

해당 색종이가 있고 check 메서드가 true로 반환되면 주석에 설명한 대로 코드를 처리한다.

 

// 색종이 붙였다가 떼는 메서드(x, y의 좌표, 무엇으로 붙일지, 사이즈의 크기)
public static void go(int x, int y, int flag, int size) {
	for(int i=0; i<size; i++) {
		for(int j=0; j<size; j++) {
			map[i+y][j+x] = flag;
		}
	}
}

색종이를 붙이고 떼는 메서드다.

flag로 0 or 1을 같이 받아서 덮어 씌우는 방법이다.

 

// 색종이 붙일 수 있는지 자리 확인하는 메서드(x, y의 좌표, 사이즈의 크기)
public static boolean check(int x, int y, int size) {
	for(int i=0; i<size; i++) {
		for(int j=0; j<size; j++) {
			// 맵을 초과했어? false 돌려준다.
			if(y+i>9 || x+j>9) {
				return false;
			}
			// 범위에 1이 없어? false 돌려준다.
			if(map[y+i][x+j]!=1) {
				return false;
			}
		}
	}
	return true;
}

색종이를 붙일 수 있는지 체크하는 메서드다.

2중 for문을 size만큼 도는데 2가지 조건을 확인해야 한다.

1. y+1>9 || x+j>9

둘 중 하나라도 색종이를 넘어서면 사이즈가 안 맞다는 소리니 false를 리턴한다.

 

2. map[y+i][x+j] != 1

해당 맵에 1이 없으면 색종이를 붙일 수 없으니 false를 리턴한다.

이 두 개가 해당되지 않으면 true를 리턴한다.