백준 17136번: 색종이 붙이기

최창효·2022년 3월 9일

문제 설명

5종류의 색종이를 각각 5개씩 가지고 있습니다.
색종이를 활용해 1을 덮어야 합니다.
색종이를 최소로 사용하여 1을 모두 덮는 경우의 수를 구하는 문제입니다.

접근법

특별한 규칙이 보이지 않고 다양한 예외상황이 존재합니다. 또한 총 경우의 수가 작기 때문에 완전탐색을 떠올려야 합니다.
완전탐색중에서도 특정 조건에 만족하는 것만 활용하는(특정 조건에 만족하지 않으면 가지치기로 탈락시킵니다) 백트래킹을 활용해야 합니다.
각 경우마다 10x10종이의 형태, 남은 색종이의 개수가 달라지기 때문에 이 둘을 백트래킹의 변수로 계속 가지고 다니는 형식으로 구현했습니다.

pseudocode

main(){
lst에 1이 적힌 곳의 좌표들을 담기
백트래킹 실행하기
}

백트래킹(){
	if(모든 1을 다 확인했다면){
		최소로 활용했는지 비교해보기
	    종료
	}
	
	if(원래 1이였던게 0으로 바껴있다면){
		해당칸은 확인했다고 체크만 하고 다음 1을 확인하러 가기
	}
	
	for(1x1종이,...,5x5종이){
		if(AxA색종이 5장을 다썼으면) 다음색종이 붙이기
		if(해당 좌표에 종이를 붙였을 때 10x10을 벗어나면) break;
		if(해당 좌표에 AxA색종이를 붙일 수 있다면){
	    	AxA색종이 붙이기
	        AxA를 붙인 상태로 다음 1을 확인하러 가기
	        AxA색종이 때기
	    }
	}
}

정답

import java.util.*;

public class Main {
	static int N = 10;
	static int min_val = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] board = new int[N][N]; //10x10종이 입니다.
		int[] usage = new int[6];
		Arrays.fill(usage, 5);

		// 1의 위치들만 담을 lst변수입니다.
		List<pos> lst = new ArrayList<pos>();
        
		// 입력값을 받습니다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt(); // board에 값을 채웁니다.
				// 1의 위치를 lst에 담습니다.
				if (board[i][j] == 1) {
					lst.add(new pos(i, j));
				}
			}
		}

		// 여기서 for문을 쓰려고 해서 복잡했다.
		BackT(lst, 0, usage, board, 0);
		
		if (min_val == Integer.MAX_VALUE) { // 최소값이 바뀌지 않았다면 내가가진 색종이로 덮을 수 없다는 뜻입니다.
			System.out.println(-1);
		} else {
			System.out.println(min_val);
		}
	}

	public static void BackT(List<pos> lst, int depth, int[] usage, int[][] board, int try_cnt) {
		// "모든 1을 다 확인했다"가 종료조건입니다.
		if (depth == lst.size()) {
			min_val = Math.min(try_cnt, min_val);
			return;
		}
		
		// depth번째 1을 덮기 위해 일단 해당 좌표를 구해옵니다.
		pos xy = lst.get(depth);
		
		// 종료조건을 depth == lst.size()로 설정했기 때문에 이 코드가 필요합니다.
		// lst에서 꺼내온 pos xy는 무조건 '처음에' 1이었던 곳입니다. (1인것만 lst에 넣었기 때문)
		// 그런 xy가 0이 되었다는 건 다른곳에서 1보다 큰 색종이를 사용하면서 함께 덮였다는 뜻입니다.
		// 우리는 종료조건을 depth == lst.size()이기 때문에 이 경우에도 확인했다는 표시로 depth를 1 증가시켜줘야 합니다.
		if (board[xy.x][xy.y] == 0) { 
			BackT(lst, depth + 1, usage, board, try_cnt); //depth만 1 증가시킵니다.
		}
		
		for (int j = 0; j < 5; j++) { // 5종류의 색종이를 나타냅니다. // j=0일 때 1x1색종이를 사용한다는 뜻입니다.
			if (xy.x + j >= N || xy.y + j >= N) break; // 가령 3x3색종이를 썼을 때 보드를 벗어난다면 3x3,4x4,5x5색종이를 꺼내서 덮어볼 필요가 없기 때문에 continue가 아니라 break을 썼습니다.

			// 색종이로 딱 맡게 덮인다 == 모든 좌표에 1이 들어있다 == 해당 좌표값들을 더했을 때 색종이 크기만큼의 값이 나온다.
			int sum = 0;
			for (int x = xy.x; x <= xy.x + j; x++) {
				for (int y = xy.y; y <= xy.y + j; y++) {
					sum += board[x][y];
				}
			}
			if ((j + 1) * (j + 1) == sum) { // 해당 색종이로 딱 맡게 덮을 수 있다면

				if (usage[j + 1] == 0) continue; // return이 아니라 continue // usage[1] == 0 && usage[j+1] == 0 이 아니라 usage[j+1] == 0만 // 시간을 줄이려고 했던 코드들이 오히려 잘못 가지치기 되어 실패

				// 해당 색종이를 사용해 덮습니다.
				usage[j + 1]--; 
				for (int x = xy.x; x <= xy.x + j; x++) {
					for (int y = xy.y; y <= xy.y + j; y++) {
						board[x][y] = 0;
					}
				}
				
				// 다음 칸을 확인하러 갑니다.
				BackT(lst, depth + 1, usage, board, try_cnt + 1);
				
				// 사용했던 색종이를 다시 땝니다.(백트래킹을 활용하기 위해)
				usage[j + 1]++;
				for (int x = xy.x; x <= xy.x + j; x++) {
					for (int y = xy.y; y <= xy.y + j; y++) {
						board[x][y] = 1;
					}
				}
			} else { // 위에 break조건과 마찬가지입니다. 3x3종이로 알맞게 덮지 못하는 곳은 4x4,5x5로도 알맞게 덮을 수 없습니다.
				break;
			}

		}

	}

	static class pos {
		int x;
		int y;

		public pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}

	}
}

기타

이 코드가 필요한 이유

if (board[xy.x][xy.y] == 0) { 
	BackT(lst, depth + 1, usage, board, try_cnt); //depth만 1 증가시킵니다.
}

다음의 경우로 예시를 들어보겠습니다.
- 1이 4개 있기 때문에 종료조건은 depth == 4입니다.
- 이 때 (0,0)에서 2x2색종이로 1을 모두 덮었다고 생각해 봅시다.
  - depth는 1을 확인했다는 의미이고 우리는 모든 1을 확인해야 올바른 종료를 할 수 있습니다.
  - 이 경우 (0,1),(1,0),(1,1)도 원래는 1이었기 때문에 우리는 확인했다는 걸 알려줘야 합니다. 그래서 다른 변화는 없지만 depth를 1 증가시켜 백트래킹을 진행하는 것입니다.