[코딩테스트] [17136] 색종이 붙이기

색종이 붙이기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

512 MB

30347

12213

6966

36.721%

문제

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

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

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

입력

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

출력

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

문제 풀이

문제 요약

• 한변의 길이가 [1, 5]인 정사각형 색종이 5종류가 각각 5장씩 있다.
• 10 * 10 색종이 위의 지정된 위치(1)에 색종이를 붙여야한다.
• 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 출력하자.
• 덮는 것이 불가능한 경우에는 -1을 출력하자.

Base Case

• 색종이를 더 이상 붙일 공간이 없는 경우

public static void solve(int row, int col, int cnt) {
	if(result <= cnt) return;
	findNext(row, col);
	if(nextRow == -1 && nextCol == -1) {
		result = cnt;
		return;
	}
}

Recursive Case

• Row, Col 좌표에 색종이를 붙일 수 있는 경우
• 1 ~ 5의 색종이를 붙일 수 있다면 재귀 함수 호출

int r = nextRow, c = nextCol;
for (int size = 1; size <= 5; size++) {
	paper[size]--;
	fill(r, c, size, 0);
	solve(r, c, cnt + 1);
	paper[size]++;
	fill(r, c, size, 1);
}

Backtrack

• 현재 붙인 색종이 수가 탐색해본 최솟값보다 큰 경우
• 색종이를 다 쓴 경우
  • 초기 색종이의 개수는 25이다. 이를 이용하여 26이상의 정수를 넣어주고 26이상이 나오면 -1을 출력
• 색종이를 붙이기에 공간이 좁은 경우

색종이가 부착 가능한 경우인지 검사

row와 col를 인자값으로 받아와서 현재 색종이의 크기를 더했을때 10을 넘어가는 경우는 제외해준다.

그리고 색종이를 붙이는 공간에 0이 있으면 안되니깐 제외한다.

public static boolean isValid(int row, int col, int size) {
	if (row + size > 10 || col + size > 10) return false; // 10 * 10를 넘어가는 경우
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			if (board[row + r][col + c] == 0) return false; // 색종이를 붙이는 공간에 0이 있는 경우
		}
	}
	return true;
}

색종이 부착

현재 색종이의 사이즈를 가져와서 열과 행을 0이나 1로 만들어준다.

public static void fill(int row, int col, int size, int color) {
	for (int r = 0; r < size; r++) {
		for (int c = 0; c < size; c++) {
			board[row + r][col + c] = color;
		}
	}
}

다음 공간 찾기

다음 공간에 1이 있다면 색종이를 붙여야할 공간이 있는 것이기에 nextRow, nextCol에 업데이트를 해주자.

public static void findNext(int row, int col) {
	for (int r = row; r < 10; r++) {
		for (int c = 0; c < 10; c++) {
			if(board[r][c] == 1) {
				nextRow = r;
				nextCol = c;
				return;
			}
		}
	} 
	nextRow = -1;
	nextCol = -1;
}

전체코드

import java.util.*;

class Main {
    static int[][] board = new int[11][11];
    static int result = 26;
    static int[] paper = {0, 5, 5, 5, 5, 5};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        
        solve(0, 0 ,0);
        System.out.println(result == 26 ? -1 : result);
    }

    static int nextRow = 0, nextCol = 0;

    static void findNext(int row, int col) {
        for (int r = row; r < 10; r++) {
            for (int c = 0; c < 10; c++) {
                if (board[r][c] == 1) {
                    nextRow = r;
                    nextCol = c; 
                    return;
                }   
            }
        }

        nextRow = -1;
        nextCol = -1;
    }

    static boolean isValid(int row, int col, int size) {
        if (row + size > 10 || col + size > 10) return false;
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                if (board[row + r][col + c] == 0) return false;
            }
        }
        return true;
    }

    static void fill(int row, int col, int size, int color) {
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                board[row + r][col + c] = color;
            }
        }
    }

    static void solve(int row, int col, int cnt) {
        if (result <= cnt) return;
        findNext(row, col);
        if(nextRow == -1 && nextCol == -1) {
            result = cnt;
            return;
        }

        

        int r = nextRow;
        int c = nextCol;
        
        for (int size = 1; size <= 5; size++) {
            if (paper[size] == 0) continue;
            if (!isValid(r, c, size)) continue;
            paper[size]--;
            fill(r, c, size, 0);
            solve(r, c, cnt + 1);
            fill(r, c, size, 1);
            paper[size]++;
        }
        
    
    }

}