[백준/BOJ] 17136번 색종이 붙이기 자바 풀이

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

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을 출력한다.

 

 

난이도 골드2의 백트래킹 문제다.

문제를 읽자마자 그리디 알고리즘을 떠올릴 수 있지만,

당장의 최적의 선택을 하면 색종이의 최소 개수가 제대로 구해지지 않는다.

그에 대한 반례는 아래와 같다.

 

 

그리디 알고리즘을 사용하면 3x3의 색종이를 가장 먼저 붙이고,

나머지를 2x2 색종이 하나와 1x1 색종이 4개를 사용하여 최소 개수는 6이 된다.

하지만 위와 같은 상황에서 색종이의 최소 개수는 3개이다.

아래처럼 2x2 색종이 두개를 세로로 붙이고, 3x3 색종이 하나를 붙이면 총 세개만으로 모든 칸을 채울 수 있기 때문이다.

즉, 그리디 알고리즘이 아닌 모든 경우를 고려하는 브루트포스의 백트래킹을 사용해야 한다.

 

		visit = new boolean[10][10];
		board = new int[10][10];
		paper = new int[5];
		
		for(int i=0;i<10;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<10;j++)
				board[i][j] = Integer.parseInt(st.nextToken());
		}

 먼저, 방문했는지 체크할 visit[][]와 입력으로 주어질 종이 board[][]를 10x10 크기로 생성한다.

또한 사용한 색종이의 개수를 저장할 paper[]를 생성한다.

인덱스 0에는 1x1 색종이를 사용한 개수를 저장하고, 인덱스 1에는 2x2 색종이를 사용한 개수를 저장할 것이다.

그리고 board[][]에 입력값을 저장한다.

 

		DFS(0, 0);
		if(answer == Integer.MAX_VALUE) {
			System.out.println(-1);
			return;
		}
		
		System.out.println(answer);

백트래킹을 수행한다.

최소 개수를 구하는 것이므로 answer를 Integer.MAX_VALUE로 초기화했다.

만약 백트래킹 수행 후 answer가 아직도 Integer.MAX_VALUE라면 한번도 갱신되지 않은 것이므로 

색종이로 모두 덮는 것이 불가능한 경우이다.

그러므로 -1을 출력하고 끝낸다.

 

	static void DFS(int depth, int cnt) {
		if(depth == 100) {
			answer = Math.min(answer, cnt);
			return;
		}
		
		int r = depth / 10;
		int c = depth % 10;
		
		if(board[r][c] == 0 || visit[r][c])
			DFS(depth + 1, cnt);
		else {
			for(int i=1;i<=5;i++) {
				if(check(r, c, i, true)) {
					DFS(depth + 1, cnt + 1);
					check(r, c, i, false);
				}
			}
		}
	}

board를 처음부터 끝까지 탐색해야 하므로 board의 인덱스가 될 depth는 0 ~ 100이 된다.

depth가 100이라면 board를 모두 탐색했다는 의미이므로 answer를 갱신한다.

 

depth에 해당하는 board값을 이미 방문했거나 색종이를 붙일 수 없는 구간이면 바로 DFS를 더 진행해준다.

색종이를 붙일 수 있다면 for문을 1부터 5까지 돈다.

1x1 색종이부터 5x5 색종이까지 붙일 수 있는 경우 붙이고, DFS를 더 진행한다.

 

 

	// flag가 true면 색종이를 붙이는 경우, false면 떼는 경우
	static boolean check(int r, int c, int num, boolean flag) {
		if(flag) {
			if(paper[num - 1] == 5)
				return false;
			
			// 붙일 수 있는지 확인
			for(int i=r;i<r+num;i++) {
				for(int j=c;j<c+num;j++) {
					if(i >= 10 || j >= 10 || visit[i][j] || board[i][j] == 0)
						return false;
				}
			}
			
			paper[num - 1]++;
		} 
		else
			paper[num - 1]--;
		
		// 색종이 붙이거나 떼기
		for(int i=r;i<r+num;i++) 
			for(int j=c;j<c+num;j++) 
				visit[i][j] = flag;
		
		return true;
	}

check() 함수를 통해 색종이를 붙일 수 있는지 확인하고, 붙일 수 있다면 색종이를 붙인다.

또한 DFS를 진행한 후 색종이를 다시 뗀다. (되돌린다)

 

매개변수 flag를 통해 색종이를 붙이는 과정인지 떼는 과정인지 확인한다.

만약 flag가 ture면 색종이를 붙이는 것이므로

가장 먼저 paper 값을 확인한다. paper가 5라면 색종이를 모두 사용한 것이므로 바로 false를 반환한다.

paper가 5가 아니라면, 매개변수 num만큼의 색종이를 붙일 수 있는지 배열의 범위, visit, board를 모두 확인한다.

붙일 수 있다면 paper를 1증가시키고, visit를 true로 만들어 색종이를 붙인다.

 

flag가 false면 색종이를 떼는 것이므로

paper를 1 감소시키고, visit를 false로 만들어 색종이를 뗀다.

 

정상적으로 색종이를 붙이거나 뗐다면 true를 반환한다.

 

 

 

 

for문으로 색종이를 붙일 수 있는지 확인하고, 일일이 붙였다 떼기 때문에

시간 초과가 뜰 거라고 생각했는데, 10x10 크기라 한 번에 맞았다.

특별한 경우를 고려할 것 없는 일반적인 백트래킹 문제라고 생각했다.

개인적으로 골드4 ~ 5 정도의 난이도인 것 같은데, 생각보다 난이도가 높은 문제라 놀랐다..

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

public class Main {
	static boolean[][] visit; 
	static int[][] board;
	static int[] paper;
	static int answer = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		visit = new boolean[10][10];
		board = new int[10][10];
		paper = new int[5];
		
		for(int i=0;i<10;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<10;j++)
				board[i][j] = Integer.parseInt(st.nextToken());
		}
		
		DFS(0, 0);
		if(answer == Integer.MAX_VALUE) {
			System.out.println(-1);
			return;
		}
		
		System.out.println(answer);
	}
	
	static void DFS(int depth, int cnt) {
		if(depth == 100) {
			answer = Math.min(answer, cnt);
			return;
		}
		
		int r = depth / 10;
		int c = depth % 10;
		
		if(board[r][c] == 0 || visit[r][c])
			DFS(depth + 1, cnt);
		else {
			for(int i=1;i<=5;i++) {
				if(check(r, c, i, true)) {
					DFS(depth + 1, cnt + 1);
					check(r, c, i, false);
				}
			}
		}
	}
	
	// flag가 true면 색종이를 붙이는 경우, false면 떼는 경우
	static boolean check(int r, int c, int num, boolean flag) {
		if(flag) {
			if(paper[num - 1] == 5)
				return false;
			
			// 붙일 수 있는지 확인
			for(int i=r;i<r+num;i++) {
				for(int j=c;j<c+num;j++) {
					if(i >= 10 || j >= 10 || visit[i][j] || board[i][j] == 0)
						return false;
				}
			}
			
			paper[num - 1]++;
		} 
		else
			paper[num - 1]--;
		
		// 색종이 붙이거나 떼기
		for(int i=r;i<r+num;i++) 
			for(int j=c;j<c+num;j++) 
				visit[i][j] = flag;
		
		return true;
	}

}