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

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

17136번: 색종이 붙이기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_BOJ_17136 {
	static class Pos{
		int y;
		int x;
		Pos(int y, int x){
			this.y=y;
			this.x=x;
		}
	}
	static int[][] map=new int[10][10];
	static int[] papers= {0,5,5,5,5,5};
	static ArrayList<Pos> ones=new ArrayList<>();
	static boolean isPossible=true;
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		for (int i=0; i<10; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=0; j<10; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if (map[i][j]==1) ones.add(new Pos(i,j));
			}
		}
		dfs(papers,0);
		if (answer!=Integer.MAX_VALUE) {
			System.out.println(answer);
		}
		else {
			System.out.println(-1);
		}
		
	}
	private static void dfs(int[] papers, int cnt) {
		if (answer<cnt) return;
		boolean isAllCovered=true;
		int y=0, x=0;
		for (int i=0; i<ones.size(); i++) {
			Pos o=ones.get(i);
			if (map[o.y][o.x]==1) {
				y=o.y;
				x=o.x;
				isAllCovered=false;
				break;
			}
		}
		if (isAllCovered) {
			answer=Math.min(answer, cnt);
			return;
		}
		for (int i=5; i>=1; i--) {
			if (check(y,x,i) && papers[i]>0) {
				mark(y,x,i);
				papers[i]-=1;
				dfs(papers, cnt+1);
				unmark(y,x,i);
				papers[i]+=1;
			}
		}
	}
	private static void unmark(int y, int x, int length) {
		for (int i = y; i < y+length; i++) {
			for (int j = x; j < x+length; j++) {
				map[i][j]=1;
			}
		}
		
	}
	private static void mark(int y, int x, int length) {
		for (int i = y; i < y+length; i++) {
			for (int j = x; j < x+length; j++) {
				map[i][j]=0;
			}
		}
	}
	private static boolean check(int y, int x, int length) {
		if (y+length>10 || x+length>10) return false;
		for (int i = y; i < y+length; i++) {
			for (int j = x; j < x+length; j++) {
				if (map[i][j]==0) return false;
			}
		}
		return true;
	}
	
}

처음에는 Greedy한 방식으로, 5x5 종이가 붙여지는 곳을 탐색해서 그곳을 0으로 바꿔주고->4x4 종이가 붙여지는 곳을 탐색해서 그곳을 0으로 바꿔주고.. 하는 방식을 택했는데 반례가 있었다. 

 

잘 생각해보니 DFS로 나올 수 있는 모든 경우를 탐색해서 최소값을 찾는.. 전형적인 문제였다.

 

우선 1이 나온 위치를 arraylist에 저장한다.

DFS 탐색 방식은 다음과 같다.

-1이 나온 위치가 모두 0으로 커버되었을 경우, 답안을 갱신하고 리턴

-모두 0으로 커버되지 않았을 경우, 커버되지 않은 위치부터 시작해 길이 1~길이 5까지 for문을 돌려주면서,

다음과 같은 과정을 거친다.

 -해당 길이를 붙일 수 있는지 체크(check) 함수

 -붙일 수 있으면 종이 개수가 남아있는지 체크 (papers[i] 체크)

 위 두 조건이 모두 만족하면 해당 영역을 0으로 마킹하여(mark함수) 체크를 해주고, paper[i]를 감소시키고, 다시 dfs 탐색을 시작한다.

 dfs탐색이 종료되면, 체크한 부분을 원래대로 1로 돌려놓고(unmark 함수) paper[i]를 다시 증가시킨다.

 

뭔가 그리디한 방식으로 접근했다가는 잘 틀릴 수 있는 문제였다.

그리고 DFS로 가능한 경우를 모두 탐색하는 방법을 떠올리는 것도 어려웠다.

 

다른 분(https://daily-life-of-bsh.tistory.com/141) 의 코드를 보니, 

별도로 1이 나온 위치를 저장할 필요 없이 아예 dfs 파라미터에 위치를 넣어주어 탐색하려는 위치에 1이 있으면 탐색을 하는 것으로 할 수 있었다. 탐색할 수 없으면 r,c+1 혹은 r+1, 0를 해주면 된다.. 

또한 answer 값이 현재 cnt보다 이미 작은 값이 나왔을 경우 리턴해주어 가지치기를 해주고,

for문을 돌 때 5부터 시작해야 더 효율성이 높아진다(큰 종이부터 체크해야 최솟값이 탐색 앞부분에서 나오므로).

 

이렇게 바꾸니 332ms->288ms로 줄어든걸 볼 수 있었다.