[Java] BOJ 17136번 색종이 붙이기

17136번: 색종이 붙이기

---

풀이

각 종이를 붙일 수 있는 모든 경우를 구해 해결했습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int answer;
	public static int[][] area = new int[10][10];
	public static int[] colorPaperCnt = {0, 5, 5, 5, 5, 5};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		for (int i = 0; i < 10; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 10; ++j) {
				area[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		answer = Integer.MAX_VALUE;
		go(0, 0, 0);
		answer = (answer == Integer.MAX_VALUE) ? -1 : answer;
		System.out.println(answer);
	}
	
	public static void go(int y, int x, int cnt) {
		if (y == 10) {
			for (int i = 0; i < 10; ++i) {
				for (int j = 0; j < 10; ++j) {
					if (area[i][j] > 0) {
						return;
					}
				}
			}
			
			answer = (answer > cnt) ? cnt : answer;
			return;
		}
		
		if (x >= 10) {
			go(y + 1, 0, cnt);
			return;
		}
		
		if (area[y][x] == 0) {
			go(y, x + 1, cnt);
		}
		else if (area[y][x] > 0) {
			for (int size = 5; size >= 1; size--) {
				if (!isPossible(y, x, size) || colorPaperCnt[size] <= 0) {
					continue;
				}
				
				colorPaperCnt[size]--;
				colorPaper(y, x, 0, size);
				go(y, x + 1, cnt + 1);
				colorPaperCnt[size]++;
				colorPaper(y, x, 1, size);
			}
		}
	}
	
	public static void colorPaper(int y, int x, int n, int size) {
		for (int i = y; i < y + size; ++i) {
			for (int j = x; j < x + size; ++j) {
				area[i][j] = n;
			}
		}
	}
	
	public static boolean isPossible(int y, int x, int size) {
		if (y + size > 10 || x + size > 10) {
			return false;
		}
		
		for (int i = y; i < y + size; ++i) {
			for (int j = x; j < x + size; ++j) {
				if (area[i][j] == 0) {
					return false;
				}
			}
		}
		
		return true;
	}
}

---

pyo7410/Algorithm