[BOJ] 17136 색종이 붙이기 (Java)

1. 문제 링크

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

17136번: 색종이 붙이기

 

2. 접근법

1. 변수 선언

cntOne: 1이 적힌 칸의 개수 (1이 적힌 모든 칸을 방문했는지의 여부를 판단하기 위해)

numOfPapers[]: 색종이 사이즈당 남은 색종이의 수

board[][]: 입력

 

2. backTracking(int depth)

색종이를 붙일 때마다 depth 증가

즉, depth가 붙인 색종이의 수이므로 최솟값을 담은 ans와 비교하여 depth가 더 크다면 종료

또한 cntOne을 사용하여 1이 적힌 칸이 남아있지 않다면, ans와 비교하여 종료

 

이중 for문으로 board를 탐색하면서 1이 적힌 칸을 만났다면,

해당 칸(i, j)를 기준으로 calcualteMaxPaperSize() 함수를 통해 덮을 수 있는 색종이의 최대 사이즈 구하기

 

maxSize부터 1까지, 각 사이즈에 대하여 해당 칸(i, j)를 덮는 경우로 나누어 재귀적으로 backTracking()을 호출하여 탐색 이어가기

 

 각 사이즈의 색종이로 덮을 때, 해당 색종이가 더이상 남지 않았다면 (numOfPapers[size] == 0) 건너뛰기

그렇지 않다면, 해당 사이즈의 색종이 개수 줄이기

 

(i, j)를 기준으로 size만큼 board[][]를 0으로 바꾸기

이때 바꾼 칸의 개수를 cntOfDeleted 변수를 사용하여 저장하기

cntOne에 cntOfDeleted만큼 빼서 남은 1이 적힌 칸의 개수 구하기

 

backTracking(depth +1)을 호출해서 이후 덮을 색종이를 탐색해나감

 

 backTracking() 이후에는 cntOne과 board[][], numOfPapers[]를 복구함

 

3. calculateMaxPaperSize(int r, int c)

(r, c)칸이 가장 왼쪽 위에 위치한 경우, 덮을 수 있는 색종이의 최대 사이즈 구하기

주변을 탐색해서 모두 1로 구성되어 있는지 판별함

 

3. 코드

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

// 색종이 붙이기

public class BJ17136 {

    static int cntOne;       // 1이 적힌 칸의 개수
    static int ans = Integer.MAX_VALUE;
    static int[] numOfPapers = {0, 5, 5, 5, 5, 5};
    static boolean[][] board = new boolean[10][10];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for(int i = 0; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 10; j++) {
                if(st.nextToken().equals("1")) {
                    board[i][j] = true;
                    cntOne++;
                }
            }
        }

        backTracking(0);

        if(ans == Integer.MAX_VALUE) ans = -1;
        System.out.println(ans);
    }

    private static void backTracking(int depth) {       // depth는 붙인 색종이 개수

        if(depth >= ans) return;                        // 최솟값보다 크다면 종료
        if(cntOne == 0) {                               // 1이 적힌 칸이 남지 않았다면, 즉 색종이로 모두 덮었다면
            ans = Integer.min(ans, depth);
            return;
        }

        for(int i = 0; i < 10; i++) {
            for(int j = 0; j < 10; j++) {
                if(board[i][j]) {                                   // 1이 적힌 칸을 만났을 때
                    int maxSize = calculateMaxPaperSize(i, j);      // 해당 칸을 기준으로 덮을 수 있는 색종이의 최대 사이즈

                    for(int size = maxSize; size >= 1; size--) {    // 각 사이즈에 대하여 덮는 경우를 나누어 탐색

                        // size에 해당하는 색종이가 더이상 남지 않았다면 패스
                        if(numOfPapers[size] == 0) continue;
                        // size에 해당하는 색종이 개수 줄이기
                        numOfPapers[size]--;

                        int cntOfDeleted = 0;
                        // (i, j)를 기준으로 size만큼 board[][]를 0으로 바꾸기
                        for(int r = i; r < i + size; r++) {
                            for(int c = j; c < j + size; c++) {
                                board[r][c] = false;
                                cntOfDeleted++;
                            }
                        }
                        // 1이 적힌 칸은 줄어듦
                        cntOne -= cntOfDeleted;

                        backTracking(depth + 1);

                        // 1이 적힌 칸 복구
                        cntOne += cntOfDeleted;
                        // board[][]를 1로 복구
                        for(int r = i; r < i + size; r++) {
                            for(int c = j; c < j + size; c++) {
                                board[r][c] = true;
                            }
                        }
                        // size에 해당하는 색종이 개수 복구
                        numOfPapers[size]++;
                    }

                    return;     // 1이 적힌 칸을 만났으면 색종이로 덮어야 했는데, 그러지 못하고 도달했으므로 유효하지 않은 탐색이기에 종료
                }
            }
        }
    }

    private static int calculateMaxPaperSize(int r, int c) {

        // (r, c)를 기준으로 덮을 수 있는 색종이의 최대 사이즈 계산하기
        for(int cnt = 1; cnt <= 4; cnt++) {
            for(int i = r; i <= r + cnt; i++) {
                for(int j = c; j <= c + cnt; j++) {
                    if(i >= r + cnt || j <= c + cnt) {
                        if(i >= 10 || j >= 10 || !board[i][j]) return cnt;
                    }
                }
            }
        }

        return 5;
    }


}

 

4. 막힌 부분

backTracking 종료 조건을 캐치하는 데 어려움이 있었다.

 

1.

처음에 backTracking()에 파라미터를 넘겨주지 않고 구현했었다.

답은 numOfPapers[] 에 남은 색종이 수가 담겨있기에, 해당 배열을 사용해서 사용한 색종이 수를 답으로 구했었다.

 

그런데 backTracking의 depth가 결국 붙인 색종이 수이므로, depth를 사용해서 답을 구하는 것이 더 깔끔한 풀이였고

최솟값을 답으로 구해야 했기에 backTracking 함수 내에서 if문을 걸어 종료 조건을 추가하는 것이 더욱 효율적으로 코드를 짜는 방법이었다.

 

2.

1이 적힌 칸은 만났다면 무조건 해당 칸을 색종이로 덮을 수 있어야 하는데, 즉 backTracking()을 재호출해야 한다.

그런데 그러지 못한 경우, 색종이로 덮지 못했다는 의미이므로 탐색을 종료해야 한다. 이걸 못 찾았다!! 그래서 무한 루프에 빠지는 케이스가 있었다.

 

 

---

재귀는 어렵다..

일단 감으로 구현은 할 수 있는데 구현하고도 내 코드가 어떻게 동작하는지 따라가야 이해할 수 있었던 풀이였다. (엉망진창..)

백트래킹 유형의 경우 종료 조건을 찾아낸 후 구현하도록 하자.