[백준 알고리즘] 백준 17136번 색종이 붙이기 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 17136번 색종이 붙이기 자바(Java)

1) 문제번호 : 17136번

 

2) 문제 출처

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

2. 문제

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

<그림 1>

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

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

 

3. 제약사항

- 

4. 입력

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

 

5. 출력

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

 

6. 풀이

- 풀이 내용은 소스코드에 주석을 참고하면 된다.

7. 소스 코드

import java.util.*;

public class Main {
	static int[][] map; // 색종이 맵
	static int[] map_number = { 5, 5, 5, 5, 5 }; // 색종이 개수 각 5개씩
	static int result = Integer.MAX_VALUE; // 색종이 개수

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

		map = new int[10][10]; // 10X10 색종이

		// 색종이 배열 입력
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		DFS(0, 0, 0);

		// result가 Integer.MIN_VALUE라면 -1 출력하고, 아니면 result 출력
		if (result == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(result);
	}

	// DFS + 백트래킹을 해서 풀기
	public static void DFS(int r, int c, int count) {
		// (0,0)부터 마지막(9,9)까지 갈 경우에 색종이 최소값 구한다.
		if (r >= 9 && c > 9) {
			result = Math.min(result, count);
			return;
		}

		// count가 result보다 크거나 같으면 시간 낭비이기 때문에 종료.
		if (count >= result) return;

		// 줄마다 마지막 칸을 넘을 경우 다음 줄로 가기
		if (c > 9) {
			DFS(r + 1, 0, count);
			return;
		}

		// 색종이 제일 큰 것부터 붙여보자.
		// 배열 값에 1이 있으면
		if (map[r][c] == 1) {
			// 색종이를 큰 것부터 준비.
			
			for (int i = 4; i >= 0; i--) {
				// 근데, 색종이가 있을 경우에 붙인다.
				// 색종이가 있으면 색종이의 크기만큼 붙일 수 있으면
				if(map_number[i]>0 && possible(r, c, i+1)) {
					// 색종이 붙여. i에 1을 더한 이유는 0~4까지 1,2,3,4,5로 해놔서.
					attach(r, c, i+1);
					
					// 색종이 개수 줄여.
					map_number[i]--;
					
					// 계속 붙여보자.
					DFS(r, c+1, count+1);
					
					// 색종이 떼.
					detach(r, c, i+1);
					
					// 색종이 땠으니까 개수 늘려.
					map_number[i]++;					
				}
			}
		}

		// 배열 값에 1이 없으면
		else DFS(r, c + 1, count);
	}

	// 색종이 붙이기
	public static void attach(int r, int c, int size) {
		for (int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				map[i][j] = 0;
			}
		}
	}

	// 색종이 떼기
	public static void detach(int r, int c, int size) {
		for (int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				map[i][j] = 1;
			}
		}
	}
	
	//색종이의 크기만큼 붙일 수 있는지 확인
	public static boolean possible(int r, int c, int size) {
		//색종이의 size만큼 확인을 하는데,
		for(int i=r;i<r+size;i++) {
			for(int j=c;j<c+size;j++) {
				//범위를 벗어나거나 그 위치가 1이 아니라면 false 리턴
				if(!isIn(i, j) || map[i][j]!=1) return false;
			}
		}
		return true;
	}
	
	// 색종이 범위 내에 있는지 확인
	public static boolean isIn(int r, int c) {
		return r >= 0 && c >= 0 && r < 10 && c < 10;
	}
}

---