[17136] 색종이 붙이기 - Java[자바]

 

 

| 문제 링크

 

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

17136번: 색종이 붙이기

 

 

 

---

 

 

 

 

| 문제

 

1. 1x1, 2x2, ..., 5x5 크기의 색종이가 5장씩 있습니다.
2. 10x10 크기의 종이가 2차원 배열(0과 1)로 주어집니다.
3. 색종이로 1만 모두 가릴 수 있는 최소한의 수를 출력하시오.
   만약 주어진 색종이로 1을 모두 가릴 수 없는 경우 -1을 출력하시오.

 

 

 

---

 

 

 

 

| 풀이

 

1. 탐색을 시작하기 전에 행, 열 좌표, 칸수 i(1<=i<=5)가 주어졌을 때, 행, 열 좌표로 부터 ixi 크기가 인덱스의 범위를 벗어나지 않고, 1로만 이루어져 있는지 확인하는 메서드를 구현합니다.
2. 입력된 2차원 배열을 (0,0)부터 열을 1씩 증가시키며 탐색하며, 9열까지 탐색한 경우 (1,0)에서 다시 탐색을 이어나가는 방식으로 9행까지 모두 탐색합니다.
   사용하는 메서드: color(int row, int col, int cnt), row: 행, col:열, cnt: 사용한 색종이 개수
3. 탐색 도중 1을 만나는 경우, 5x5색종이 부터 1x1 색종이까지 1번에서 구현한 메서드를 사용해 색종이를 사용할 수 있는지 확인하며, 해당 색종이의 개수가 부족하지는 않는지 확인합니다.
4. 3번의 조건을 만족하는 경우 해당 ixi 크기의 값을 0으로 바꾸고, 해당 크기의 색종이의 개수를 -1합니다.
5. 2번에서 사용한 메서드를 col과 cnt를 +1씩 증가시켜 재귀함수를 수행합니다.
6. 재귀를 종료하고 나오면 해당 ixi 크기의 값을 다시 1로 바꾸고, 해당 크기의 색종이의 개수를 +1합니다.
7. 만약 3번에서 탐색 값이 1이 아닌 0이라면, 2번에서 사용한 메서드를 col만 +1 증가시켜 재귀함수를 수행합니다.
8. 9행까지 모두 탐색한 경우 cnt가 min 값인 경우 min 값을 갱신합니다.
   만약 9행까지 도달하지 않았더라도 cnt가 min보다 큰 경우에는 더 이상 탐색하는 것이 무의미해 return해 백트래킹해줍니다.
9. 3번에서 색종이의 수가 부족해 탐색을 이어나가지 못하는 경우(min값이 초기값이랑 동일) -1을 출력,
   모든 탐색을 완료했다면 min 값을 출력.

 

 

!pro tip

색종이의 크기를 5x5 부터 4x4, ..., 1x1 순으로 확인하는 경우와 1x1, 2x2, ..., 5x5 순으로 확인하는 경우는 효율성 차이가 있음을 공유 드립니다.

 

윗 풀이: 1x1, 2x2, ... 5x5 순으로 탐색

아래 풀이: 5x5, 4x4, ..., 1x1 순으로 탐색

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int min;
	public static int[][] arr;
	//크기별 종이의 개수
	public static int[] paper = {0,5,5,5,5,5};

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		arr = new int[10][10];
		min = Integer.MAX_VALUE;
		
		//10x10 종이의 값을 입력 받음
		for(int r = 0; r<10; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c = 0; c<10; c++) {
				arr[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		//색종이 탐색 시작
		color(0,0,0);
		//색종이가 부족해 모든 범위에 대해 탐색을 완료하지 못했다면 -1출력, 아니라면 최소한으로 사용한 색종이수 min 출력
		if(min != Integer.MAX_VALUE)
			bw.write(String.valueOf(min));
		else
			bw.write("-1");
		br.close();
		bw.close();
		
	}
	
	public static void color(int row, int col, int cnt) {
		//탐색 도중 min보다 cnt의 값이 크다면 확인할 필요 없어 백트래킹
		if(cnt>=min) {
			return;
		}
		//열을 전부 탐색했다면, 행을+1 하며 0열부터 다시 탐색 시작
		if(col==10) {
			color(row+1,0,cnt);
			return;
		}
		//행까지 모두 탐색했다면 min 값 초기화
		if(row==10) {
			min = Math.min(min, cnt);
			return;
		}
		//탐색하는 좌표의 값이 1이라면 크기별 색종이로 대체 시도
		if(arr[row][col]==1) {
			//5x5부터(큰 색종이부터) 효율성을 높임
			for(int i = 5; i>=1; i--) {
				//ixi 크기의 색종이 사용이 불가능하거나, 해당 색종이의 개수가 없다면 continue;
				if(!possible(row,col,i) || paper[i]==0)
					continue;
				//종이에 ixi 크기의 범위의 값을 0으로 바꿈 
				for(int r = row; r<row+i; r++) {
					for(int c = col; c<col+i; c++) {
						arr[r][c] = 0;
					}
				}
				//ixi 색종이는 사용해 -1
				paper[i]--;
				//col과 cnt를 +1씩 더하고 재귀함수 호출
				color(row,col+1,cnt+1);
				//해당 재귀까지 모두 끝난 경우 ixi 범위와 색종이 개수를 원복함(다른 크기의 색종이 사용의 경우를 확인하기 위해)
				for(int r = row; r<row+i; r++) {
					for(int c = col; c<col+i; c++) {
						arr[r][c] = 1;
					}
				}
				paper[i]++;
			}
		}
		//탐색 좌표의 값이 1이 아닌 경우 col만 +1 증가시키고 재귀함수 호출
		else
			color(row,col+1,cnt);
	}
	
	//특정 좌표로 부터 ixi 범위가 인덱스를 벗어나지 않고, 모두 1로 이루어져 있는지 확인
	public static boolean possible(int row, int col, int num) {
		for(int r = row; r<row+num; r++) {
			for(int c = col; c<col+num; c++) {
				if(r>=10 || c>=10 || arr[r][c]==0)
					return false;
			}
		}
		
		return true;
	}

}