[백준] 17136 색종이 붙이기 - Backtracking / Java

• 문제 링크

17136번: 색종이 붙이기

 

• 풀이 과정

10 * 10 크기의 2차원 배열에 색종이를 붙일 수 있는 면적에 대한 정보를 입력받고

크기가 1 * 1 ~ 5 * 5 인 각각의 색종이의 사용 가능한 개수를 기록할 paper 배열을 생성한다.

전체 면적을 재귀 함수를 활용하여 최상단 행에서 우측으로 모두 탐색 후, (x == 10)

아래 행으로 내려가는 방식(recur(y + 1, 0, cnt)) 으로 탐색한다.

 

만약 현재 좌표가 색종이를 붙일 수 없는 좌표라면 다음 x 축으로 재귀 호출,

색종이를 붙일 수 있다면 현재 좌표는 색종이의 왼쪽 상단의 꼭지점이 된다.

 

해당 꼭지점을 기준으로 큰 크기 색종이부터 탐색하며, 해당 색종이가 사용 가능한 여분이 있는지 (papar[i] > 0)

또한 그 크기만큼 면적에 붙일 수 있는지 (canAttach(y, x, i)) 확인하여,

만약 붙일 수 있는 조건에 만족한다면 잔여 개수를 하나 소진하고, (paper[i]--)

convert 함수를 통해 색종이를 붙인 후

사용한 색종이의 개수를 1 증가시키는 재귀 호출 뒤, 원 상태로 복귀한다.

 

모든 면적의 탐색을 완료하였다면, (y == 10) 현재까지 누적된 색종이의 사용 개수와 최소값을 비교하여

최종적으로 갱신된 최소값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    static int[][] map;
    static int[] paper = {0, 5, 5, 5, 5, 5};
    static int min = Integer.MAX_VALUE;

    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;

        map = new int[10][10];

        for (int i = 0; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        recur(0, 0, 0);

        bw.write(min == Integer.MAX_VALUE ? "-1" : String.valueOf(min));
        bw.flush();
    }

    private static void recur(int y, int x, int cnt) {
        if (y == 10) {
            min = Math.min(min, cnt);
            return;
        }

        if (x == 10) {
            recur(y + 1, 0, cnt);
            return;
        }

        if (map[y][x] == 1) {
            for (int i = 5; i > 0; i--) {
                if (paper[i] > 0 && canAttach(y, x, i)) {
                    paper[i]--;
                    convert(y, x, i, 0);
                    recur(y, x + 1, cnt + 1);
                    convert(y, x, i, 1);
                    paper[i]++;
                }
            }
        } else
            recur(y, x + 1, cnt);
    }

    private static boolean canAttach(int y, int x, int size) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (y + i > 9 || x + j > 9 || map[y + i][x + j] == 0)
                    return false;
            }
        }

        return true;
    }

    private static void convert(int y, int x, int size, int state) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++)
                map[y + i][x + j] = state;
        }
    }

}