[백준 17136] 색종이 붙이기 (Java, 골드2)

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

 

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

 

[ 풀이 과정 ]

생각난 알고리즘은 브루트 포스, 백트래킹이였다.

각 크기에 맞는 색종이가 연속적으로 있는 위치를 찾아야 한다는 점에서 브루트 포스,

모든 1을 덮은 여러 경우를 depth 를 거쳐 가져야 한다는 점에서 백트래킹이 생각났다.

 

[ 처음 작성했던 코드 ]

import java.io.*;
import java.util.*;

class Main {
    public static int N = 10;
    public static int SPACE_AMOUNT = 0;
    public static int[] LEFT_PAPER = {-1, 5, 5, 5, 5, 5};
    public static int MIN = Integer.MAX_VALUE;
    public static int[][] MAP = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i=0; i<N; i++) {
            int[] line = getIntArr(br.readLine().split(" "));
            for (int j=0; j<N; j++) {
                if (line[j] == 1) SPACE_AMOUNT ++;
                MAP[i][j] = line[j];
            }
        }


        // 한 판에 각 색종이들을 최대 5개까지 사용하여 모두 채워넣어야 한다.
        // 특정 map 에 특정 색종이를 채울 수 있는지 없는지, 있다면 채워넣고 없다면 넘어가야 한다.

        backTracking(MAP, 5, SPACE_AMOUNT, 0);

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

    public static void backTracking(int[][] map, int paper, int leftSpace, int paperCount) {
//        System.out.println("paper=" + paper + ", leftSpace=" + leftSpace + ", paperCount=" + paperCount);
        if (MIN <= paperCount) return;

        if (paper == 1) {
            if (leftSpace <= LEFT_PAPER[paper]) MIN = Math.min(MIN, paperCount + leftSpace);
            return;
        }

        if (LEFT_PAPER[paper] == 0) {
            backTracking(map, paper - 1, leftSpace, paperCount);
            return;
        }

        boolean isDiscount = false;

        // 전체 map 순회
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                // 만약 해당 kind의 색종이를 붙일 수 있는 공간이 있다면,
                // 붙인 후에 새로운 맵으로 backTracking 재호출
                if (map[i][j] == 1) {
                    int[][] newMap = stickPaper(map, i, j, paper);
                    if (newMap != null) {
                        isDiscount = true;
                        LEFT_PAPER[paper] --;
                        backTracking(newMap, paper, leftSpace - paper*paper, paperCount + 1);
                        LEFT_PAPER[paper] ++;
                    }
                }
                // (원복)
                // 해당 kind의 색종이를 다른 곳에 붙이는 경우도 계산해야 하므로,
                // 기존 맵으로 계속 계산하기
            }
        }

        // 만약 해당 kind의 색종이를 못붙였다면, kind-1 색종이 backTracking 호출
        if(!isDiscount) backTracking(map, paper - 1, leftSpace, paperCount);
    }

    /**
     * 해당 paper 를 붙일 수 있다면, 붙인 이후의 newMap 반환, 아니라면 null 반환
     */
    public static int[][] stickPaper(int[][] map, int x, int y, int paper) {
        int[][] newMap = copyMap(map);

        if (x+paper > N || y+paper > N) return null;

        for (int i=x; i<x+paper; i++) {
            for (int j=y; j<y+paper; j++) {
                if (newMap[i][j] == 0) return null;
                newMap[i][j] = 0;
            }
        }

        return newMap;
    }

    public static int[][] copyMap(int[][] map) {
        int[][] newMap = new int[N][N];
        for (int i=0; i<N; i++) {
            newMap[i] = Arrays.copyOf(map[i], N);
        }
        return newMap;
    }

    private static int[] getIntArr(String[] strArr) {
        return Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
    }
}

 

그런데 자꾸 시간 초과가 떴다.

그 이유는 자꾸만 불필요한 중복 메소드를 호출하기 때문이었다.

 

[ 시간 초과 이슈에 대한 원인 찾기 ]

문제 상황

출력 사진을 보면 알 수 있듯이,

정상적인 로직이었다면 첫 5 문장만 출력되고 프로세스가 종료되어야 했다.

그러나 이 이후 아래까지 몇 십줄은 불필요한 중복 프로세스가 계속 되고 있었다.

왜 5x5 색종이로 모두 채웠는데, 다음으로 더 작은 색종이로 또 내려가는지 알아내야 했다.

 

[ 문제의 원인 ]

1. MIN 을 갱신하는 조건이 paper == 1 이거 밖에 없어서 그런가? 싶어서 추가했던 코드

if (paper * paper * paperCount == SPACE_AMOUNT) {
    MIN = Math.min(MIN, paperCount);
    return;
}

 

그러나 이 코드는 틀린 논리라는 것을 깨닫게 된다.

 

왜 틀렸을까?

 

1) 내가 생각한 의도 = paper * paper, 즉 5x5 색종이라면 5x5 = 25 의 면적이 paperCount, 즉 몇개 있는가?

2) 틀릴 수도 있는 경우 = 1x1 색종이가 100개 있다면?

 

위 두 경우를 계산해보면 같은 값이 나온다. 5x5x4 = 1x1x100

 

이런 이유 말고도.. 여러 문제들이 있다.

 

1. 색종이 크기와 덮어야 할 공간의 위치가 무관하게 계산된다.

paperCount 는 어떤 색종이가 몇 개가 배치되었는지 알 수 없기 때문이다.

 

2. 색종이를 정확히 배치할 수 없을 때도 조건을 통과해버린다.

 

3. 결론

backTracking 의 파라미터를 살펴보자.

// map : 현재 바뀐 map
// paper : 현재 붙이려는 색종이
// leftSpace : 붙이는 과정을 모두 마친 이후에 남은 공간 (채워야하는 공간)
// paperCount : 붙이는 과정을 모두 마친 이후에 최종적으로 붙인 색종이의 수
int[][] map, int paper, int leftSpace, int paperCount

map, paper 는 `현재 어떤 값인지` 를 분별하기 위해서 넣은 `거쳐가는 파라미터`이다.

그러나 leftSpace, paperCount 는 모든 한 과정이 지나고, `결론` 을 저장하기 위한 파라미터이다.

(그러나 여기서 paperCount 는 어떤 색종이가 몇 장인지는 저장하지 않기에 위험하다.)

 

따라서 조건은 다음같이 작성해야 옳다.

if (leftSpace == 0) {
    MIN = Math.min(MIN, paperCount);
    return;
}

 

 

 

.

.

.

 

Greedy 를 더 잘 이해 하고 내일 다시 고치러 와야겠다

하 ~ 어렵당

 

(수정 완료)

문제를 해결했다.

 

다음 게시글에서 확인할 수 있다.

↓

https://jinn-o.tistory.com/281

[백준 17136] 색종이 붙이기 (Java, 골드2) - 후속편

 

 

감격스러운 순간이다.