[백준] 색종이 붙이기 (JAVA)

색종이 붙이기_17136

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

17136번: 색종이 붙이기

문제 설명

길이가 10인 정사각형 종이가 있다.

이 종이에는 1로 표시된 부분이 있는데 이 부분을 색종이로 딱맞게 가려야한다.

0으로 표시된 부분을 색종이로 가릴 수 없고 색종이가 종이 밖으로 넘쳐도 안된다.

 

길이가 1부터 5까지인 정사각형을 5개씩 가지고있다.

모든 1을 가릴 수 있는 색종이의 최소 개수를 구하는 문제이다.

방법이 없는경우 -1을 출력한다.

---

문제 풀이

생각 과정

종이가 10x10이기 때문에 브루트포스로 풀어보기로 생각했다.

 

우선 1이 나온 좌표에서 길이가 몇인 색종이까지 사용한지 알려주는 can 함수를 만들었다.

1 0 1

1 1 1

0 1 1

위의 경우는 길이가 1인 색종이밖에 사용하지 못하지만

 

1 1 0

1 1 1

0 1 1

이런 경우는 길이가 1인 색종이를 사용할 수도 있고 2인 색종이도 사용할 수 있다.

 

다음으로 색종이를 사용하여 가린 경우 1이 0으로 바뀌어야 하므로 1과 0을 바꿔주는 함수 change도 만들었다.

 

종이를 0,0 부터 탐색하면서 1이 나오면 can을통해 가능한 색종이의 길이를 구해 change로 1을 지워주고 재귀함수를 돌린다.

색종이를 사용한 개수를 길이마다 저장해서 5장 넘게 사용할 수 없게 만든다.

마지막 좌표까지 도달하면 최솟값을 갱신해준다.

 

구현

public class 색종이붙이기_17136 {
    static int answer;
    static int[] cnts;
    static int[][] all;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        all = new int[10][10];	// 전체 종이
        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 10; j++) {
                all[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        cnts = new int[6];	// 각 길이마다 사용횟수 저장
        answer = -1;
        run(0, 0, 0);
        System.out.println(answer);
    }

    public static void run(int y, int x, int cnt) {
        if (x == 10) {
            run(y + 1, 0, cnt);
            return;
        }

        if (y == 10) {	// 모든 종이 순회 완료
            if (answer == -1) answer = cnt;
            answer = Math.min(answer, cnt);
            return;
        }

        if (all[y][x] == 1) {
            for (int i = 1; i <= 5; i++) {
                if (can(y, x, i)) {
                    cnts[i]++;	// i 길이 색종이 사용횟수 추가
                    change(y, x, i);
                    run(y, x + 1, cnt + 1);	// 재귀
                    change(y, x, i);
                    cnts[i]--;
                }
            }
        } else {
            run(y, x + 1, cnt);	// 다음 칸 탐색
        }
    }
	// y,x좌표에서 i길이 색종이를 사용가능한지 확인
    public static boolean can(int y, int x, int len) {
        if (cnts[len] == 5) return false;	// 5장 넘게 사용불가
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (y + i >= 10 || x + j >= 10) return false;	// 종이넘치게 불가
                if (all[y + i][x + j] != 1) return false;	// 0인 포함된 경우 불가
            }
        }
        return true;
    }
	// y,x좌표에서 i길이 만큼 1<->0을 전환
    public static void change(int y, int x, int len) {
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                all[y + i][x + j] = all[y + i][x + j] == 1 ? 0 : 1;
            }
        }
    }
}