[골드2] 17136. 색종이 붙이기(Java)

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

17136번: 색종이 붙이기

내 연휴 돌려줘요

---

※  문제를 요약하면 아래와 같습니다.

▶ 1x1 ~ 5x5 크기의 정사각형 모양 색종이가 각각 5장씩 존재, 10x10인 종이 위에 부착

▶ 겹쳐서 붙이거나 종이 경계밖으로 나가서는 안돼며, 0이 적힌 칸에는 색종이가 있으면 안됌

▶ 종이의 상태가 0과 1로 주어졌을 때, 필요한 색종의 최소 갯수 출력 

▶ Input : 10개의 줄에 종이의 각 칸에 적힌 수 입력

▶ Output : 필요한 색종이의 최소 개수 출력, 1을 모두 덮는 것이 불가능한 경우, -1 출력

---

◈ Input - 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 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 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

◈ Output - 1

0

◈ Input - 2

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 1 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 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

◈ Output - 2

4

◈ Input - 3

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

◈ Output - 3

5

◈ Input - 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 0 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

◈ Output - 4

-1

◈ Input - 5

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 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

◈ Output - 5

7

◈ Input - 6

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

◈ Output - 6

4

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 색종이의 최대 크기인 5x5 부터 탐색을 진행하여도 예외 케이스 발생

▶ 각각의 색종이 사용의 경우의 수를 전부 탐색

    (크기별로 5장씩만 사용 가능하며 크기가 작은 색종이를 먼저 사용해야 최소 사용 갯수일 경우도 존재)

▶ 색종이를 덮었는지 확인하기 위한 10x10 크기의 boolean 형 배열 선언

▶ 각 크기별 색종이의 사용 횟수 체크를 위한 int형 배열 선언

▶ 사각형 탐색을 범위 체크 + 값1 체크 + 방문 여부 조건을 설정하여 메서드(함수)로 선언

▶ 부분집합 재귀 탐색을 활용하여 완전 탐색, 색종이가 최소로 사용된 갯수를 저장

▶ 현재 탐색 중인 행과,열 사용된 색종이의 수를 재귀 함수 인자로 반환, 탐색이 더 이상 불가능한 경우 최소값 비교

▶ 재귀 과정에서 이미 최소 탐색 횟수를 넘었을 경우 탐색 종료 (빽트래킹!)

---

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int nMin, nTemp;
	static boolean[][] barrMap, barrCheck;
	static int[] narrPaper;
	final static int SIZE = 10;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		barrMap = new boolean[SIZE][SIZE];
		barrCheck = new boolean[SIZE][SIZE];
		narrPaper = new int[5];

		nMin = Integer.MAX_VALUE;

		// 색종이 입력 받자
		for (int i = 0; i < SIZE; i++) {
			StringTokenizer st = new StringTokenizer(bReader.readLine());
			for (int j = 0; j < SIZE; j++) {
				if (Integer.parseInt(st.nextToken()) == 1)
					barrMap[i][j] = true;
			}
		}
		// 가장 큰 사이즈인 5부터 검사를 시작
		// 하지만 5가 들어가있어서 더 많을 수도 있으니
		// 다른 경우도 검사해보자
		Arrays.fill(narrPaper, 5);
		
		Paper(0, 0, 0);

		if (nMin == Integer.MAX_VALUE)
			nMin = -1;

		bWriter.write(String.valueOf(nMin));
		bWriter.close();

	}

	private static void Paper(int nRow, int nCol, int nCount) {
		// 색종이가
		int nSearchRow = -1;
		int nSearchCol = -1;
		for (int i = nRow; i < SIZE; i++) {
			for (int j = nCol; j < SIZE; j++) {

				if (barrMap[i][j] && !barrCheck[i][j]) {
					nSearchRow = i;
					nSearchCol = j;
					break;
				}
			}
			if (nSearchRow != -1)
				break;
		}

		if (nSearchRow == -1) {
			if (nMin > nCount && IsDone())
				nMin = nCount;
			return;
		}
		if (nCount > nMin)
			return;

		for (int k = 5; k > 0; k--) {
			if (!barrCheck[nSearchRow][nSearchCol] && narrPaper[k - 1] > 0) {
				// 사각형인 것을 확인했다믄
				if (RectMasking(nSearchRow, nSearchCol, k)) {
					narrPaper[k - 1]--;

					Paper(nSearchRow, 0, nCount + 1);

					narrPaper[k - 1]++;
					Checking(nSearchRow, nSearchCol, k, false);
				}
			}
		}

		// 색종이가 다 붙여졌다??

	}

	// 사각형 검사
	private static boolean RectMasking(int nRow, int nCol, int nSize) {
		for (int i = nRow; i < nRow + nSize; i++) {
			for (int j = nCol; j < nCol + nSize; j++) {
				// 사각형이 될 수 없다
				// 범위 밖, 1이 없다, 이미 체크 했다
				if (i < 0 || j < 0 || i >= SIZE || j >= SIZE || !barrMap[i][j] || barrCheck[i][j])
					return false;
			}
		}
		Checking(nRow, nCol, nSize, true);
		// System.out.println(nRow + " " + nCol + " " + nSize);
		// 여기 왔다는건 사각형이라는 뜻이다.
		return true;
	}

	private static void Checking(int nRow, int nCol, int nSize, boolean bSwitch) {
		for (int i = nRow; i < nRow + nSize; i++) {
			for (int j = nCol; j < nCol + nSize; j++) {
				barrCheck[i][j] = bSwitch;
			}
		}
	}

	// 모든 1이 (색종이가) 체크가 되었나???
	private static boolean IsDone() {

		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				if (barrMap[i][j] != barrCheck[i][j]) {
					System.out.println("ROW : " + i + " / COL : " + j);
					return false;
				}
			}
		}
		return true;
	}
}

---

Good Luck! (피드백 감사합니다!)