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

문제 링크

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

17136번: 색종이 붙이기

---

💡 풀이

색종이의 크기에 따라 붙여 나아가며 붙일 수 없는 경우 되돌아오는 백트래킹을 이용하여 풀이 할 수 있습니다. 

그래프의 (0, 0)부터 차례대로 탐색하며, 0인 경우 옆으로 넘어가고, 1인 경우 붙일 수 있는 여부를 확인해 진행하는 방식을 이용했습니다.

BackTracking

백트래킹 함수의 파라미터로는 ( y좌표, x좌표, 지금까지 사용한 색종이 수) 이렇게 3가지를 사용합니다. 

이에 따라 함수가 종료되는 Base Case와 함수가 동작하는 Recursive Case를 살펴보면 다음과 같습니다.

Base Case

우선, 파라미터로 y 좌표와 x 좌표가 입력되기 때문에, x 좌표값이 전체 그래프 길이인 10, 여기서는 인덱스를 사용하므로 9를 넘어간다면, 다음 줄로 이동하도록 설정합니다. 

// Base Case
// 가로 끝에 도달하면 다음 줄로 내려가기
if (x > 9) {
    backTracking(y + 1, 0, count);
    return;
}

 

또, y 좌표가 9보다 커진다면 모든 줄의 탐색을 완료한 것이기 때문에 지금까지 구한 사용된 색종이의 개수와 기존 정답을 비교해 정답을 갱신해줍니다.

// 마지막 줄까지 검사를 마친 경우
if (y > 9) {
    if (answer == -1) {
        answer = count;
    } else if (answer > count) {
        answer = count;
    }
    return;
}

 

마지막으로 현재 (y, x) 위치의 값이 0이어서 색종이를 놓을 수 없는 경우 다음으로 즉, 가로로 한 칸 이동하도록 합니다.

// 현재 위치가 종이를 놓을 수 없으면 가로로 한 칸 이동
if (graph[y][x] == 0) {
    backTracking(y, x + 1, count);
    return;
}

 

Recursive Case

다음은 백트래킹이 동작하는 부분입니다.

우리가 구해야 할 값은 사용하는 색종이의 최소값입니다. 색종이를 최소로 사용하기 위해서는 큰 종이부터 붙여 나가야 합니다. 따라서, 가장 큰 색종이부터 탐색을 시작합니다. 

여기서, 다음 3가지의 경우는 색종이를 붙일 수 없는 경우입니다.

1. 보유한 색종이를 모두 사용한 경우
2. 색종이를 붙였을 때 그래프의 범위를 벗어난 경우
3. 0에 걸려 색종이로 채울 수 없는 경우

위의 조건을 확인하며 재귀 함수를 구현해주면 됩니다.

// Recursive Case
// 큰 종이부터 붙여 나아가야 최소로 덮을 수 있다.
for (int size = 5; size > 0; size--) {
    // 보유한 색종이를 모두 사용한 경우
    if(papers[size] == 0) continue;
    // 색종이를 붙였을 때 범위를 벗어나는 경우
    if(y + size > LEN || x + size > LEN) continue;
    // 색종이로 채울 수 없는 경우
    if(!canFill(y, x, size)) continue;

    // 색종이로 채우기
    papers[size]--;
    fill(y, x, size, 0);
    backTracking(y, x + 1, count + 1);
    // 돌아와서 다시 1로 채우기
    papers[size]++;
    fill(y, x, size, 1);
}

 

여기서 canFill 함수는 색종이를 채울 수 있는지를 검사하는 메서드입니다. 

static boolean canFill(int y, int x, int size) {
    for (int row = y; row < y + size; row++) {
        for (int col = x; col < x + size; col++) {
            if (graph[row][col] == 0) {
                return false;
            }
        }
    }
    return true;
}

 

fill 은 0 또는 1로 지정된 범위의 그래프 값을 채워주는 함수입니다.

static void fill(int y, int x, int size, int flag) {
    for (int row = y; row < y + size; row++) {
        for (int col = x; col < x + size; col++) {
            graph[row][col] = flag;
        }
    }
}

 

전체 코드

전체적인 코드는 다음과 같습니다.

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

public class Q17136 {
    static final int LEN = 10;
    static int answer;
    static int[] papers = {0, 5, 5, 5, 5, 5};
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        graph = new int[LEN][LEN];
        for (int y = 0; y < LEN; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < LEN; x++) {
                graph[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        answer = -1;
        backTracking(0, 0, 0);
        System.out.println(answer);
    }

    static void backTracking(int y, int x, int count) {
        // Base Case
        // 가로 끝에 도달하면 다음 줄로 내려가기
        if (x > 9) {
            backTracking(y + 1, 0, count);
            return;
        }
        // 마지막 줄까지 검사를 마친 경우
        if (y > 9) {
            if (answer == -1) {
                answer = count;
            } else if (answer > count) {
                answer = count;
            }
            return;
        }
        // 현재 위치가 종이를 놓을 수 없으면 가로로 한 칸 이동
        if (graph[y][x] == 0) {
            backTracking(y, x + 1, count);
            return;
        }

        // Recursive Case
        // 큰 종이부터 붙여 나아가야 최소로 덮을 수 있다.
        for (int size = 5; size > 0; size--) {
            // 보유한 색종이를 모두 사용한 경우
            if(papers[size] == 0) continue;
            // 색종이를 붙였을 때 범위를 벗어나는 경우
            if(y + size > LEN || x + size > LEN) continue;
            // 색종이로 채울 수 없는 경우
            if(!canFill(y, x, size)) continue;

            // 색종이로 채우기
            papers[size]--;
            fill(y, x, size, 0);
            backTracking(y, x + 1, count + 1);
            // 돌아와서 다시 1로 채우기
            papers[size]++;
            fill(y, x, size, 1);
        }
    }

    static boolean canFill(int y, int x, int size) {
        for (int row = y; row < y + size; row++) {
            for (int col = x; col < x + size; col++) {
                if (graph[row][col] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    static void fill(int y, int x, int size, int flag) {
        for (int row = y; row < y + size; row++) {
            for (int col = x; col < x + size; col++) {
                graph[row][col] = flag;
            }
        }
    }
}