[백준 JAVA] 17136번: 색종이 붙이기

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

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

public class Main {
	public static int N = 10, ans;
	public static int[] p_cnt = new int[5];
	public static int[][] map = new int[N][N];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		// 1. 입력받기
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		ans = Integer.MAX_VALUE;

		// 2. 색종이 붙이기
		dfs(0, new int[6], 0);

		// 4. 출력하기

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

	public static void dfs(int at, int[] num, int cnt) {
		if(cnt > ans) {
			return;
		}
		for (int i = at; i < N * N; i++) {
			if (map[i / N][i % N] == 1) {
				// 3. 큰 색종이부터 검사
				for (int j = 5; j >= 1; j--) {
//					if (i / N + j >= N || i % N + j >= N)
//						continue;
					if (num[j] < 5 && check(i / N, i % N, j)) {
						// 3-1. 붙일 수 있다면 종이 수 감소 후 방문처리
						num[j]++;
						fill(i / N, i % N, j, 0);
						dfs(i + 1, num, cnt + 1);
						num[j]--;
						fill(i / N, i % N, j, 1);
					}
				}
				return;
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1)
					return;
			}
		}

		if (cnt < ans) {
			ans = cnt;
		}
	}

	public static boolean check(int r, int c, int size) {
		for (int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				if(i >= N || j >= N) return false;
				if (map[i][j] == 0)
					return false;
			}
		}
		return true;
	}

	public static void fill(int r, int c, int size, int k) {
		for (int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				map[i][j] = k;
			}
		}
	}
}

 

## 풀이 사항
풀이 일자: 2024.09.12
풀이 시간: 60분
채점 결과: 정답
예상 문제 유형: DFS

## 풀이 방법
1. 맵 전체를 DFS (조합)으로 돌며 1을 만나면 큰 색종이부터 순차적으로 붙일 수 있는지 체크 한 뒤, 붙일 수 있다면 쓴 색종이 수를 늘리고 0으로 채워준다.
2. dfs을 다 돌고 빠져 나왔다면 다시 1로 초기화 해준다. 
3. 색종이를 붙이지 못한다면 어차피 위에서 아래로, 좌측에서 우측으로 순회하며 붙이기 때문에 끝까지 다 돌아도 붙이지 않는 구역이 되버린다. 따라서 더이상 dfs를 들어가거나 맨 마지막에 검사해줄 필요가 없으므로 return 해준다.
4. 맵의 마지막까지 성공적으로 색종이를 붙였다면 맵에 1이 있는지 확인하고 없다면 ans의 최솟값을 갱신해준다.
5. dfs를 들어갈때 만약 정답보다 색종이를 붙인 횟수가 많아졌다면 어차피 정답이 아니므로 백트래킹해준다.