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

📖 문제

17136번: 색종이 붙이기

 

 

💡  풀이 방식

• 브루트포스 + 백트래킹

- 최소 색종이 갯수 사용  ⇒ 큰 종이부터 붙이기 ⇒ 그리디

- 완전탐색 ⇒  브루트포스 + 백트래킹

- N X N 범위 내에 모두 1이 존재한다면, N X N 색종이를 붙였다 떼는 작업 반복

 

1. 종이 배열에 종이의 최대 갯수 저장

2. DFS 활용해 백트래킹 시도

  - 기본 탐색 방향 : 가로

  - 끝 칸 도착 시, 아랫줄 첫 칸으로 이동

3. 좌표가 맨 마지막 점 도달 시, 지금까지 붙인 종이 갯수 반환

 

 

💥 유의사항

[종료 조건] x가 9이고, y가 10일 때

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] paper = {0, 5, 5, 5, 5, 5};    // 각 종이의 남은 갯수 저장 배열
    
    static int[][] map = new int[10][10];
    
    static int ans = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        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());
            }
        }
        
        dfs(0, 0, 0); // (0,0)부터 오른쪽 아래로 이동하며 색종이 덮어 나감
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
    
    // DFS + 백트래킹
    private static void dfs(int r, int c, int cnt) {
        // 맨 끝 점 도달 시 종료
        if(r >= 9 && c > 9) {
            ans = Math.min(ans, cnt);
            return;
        }
        
        // 최솟값 계산하는데 cnt가 ans보다 커지는 순간, 더 이상 탐색할 필요 X
        if(ans <= cnt) {
            return;
        }
        
        // 오른쪽으로 이동하다 범위 벗어나면 아래 줄로 이동
        if(c > 9) {
            dfs(r + 1, 0, cnt);
            return;
        }
        
        if(map[r][c] == 1) {
            for(int i = 5 ; i >= 1 ; i--) { // 제일 큰 색종이 크기부터 붙일 수 있는지 확인 (그리디)
                if(paper[i] > 0 && isAttach(r, c, i)) {
                   attach(r, c, i, 0); // 현재 위치에 i 크기의 색종이 붙임
                    paper[i]--;
                    dfs(r, c + 1, cnt + 1);
                    attach(r, c, i, 1); // 붙였던 색종이 다시 뗌
                    paper[i]++;
                }
            }
        }
        else {  // 현재 위치에 색종이 둘 수 없으면, 오른쪽으로 이동
            dfs(r, c + 1, cnt);
        }
    }
    
    // 색종이 붙이고 떼는 메소드
    private static void attach(int r, int c, int size, int state) {
        for(int i = r ; i < r + size ; i++) {
            for(int j = c ; j < c + size ; j++) {
                map[i][j] = state;
            }
        }
    }
    
    // 색종이 붙일 수 있는지 확인
    private static boolean isAttach(int r, int c, int size) {
        for(int i = r ; i < r + size ; i++) {
            for(int j = c ; j < c + size ; j++) {
                if(i < 0 || i >= 10 || j < 0 || j >= 10)
                    return false;
                    
                if(map[i][j] != 1)
                    return false;
            }
        }
        
        return true;
    }
}
 

 

 

 

---

💦 어려웠던 점

- 큰 종이부터 사용할 생각은 했는데 어떻게 오른쪽 아래 갯수를 (+1,+1)씩 증가시키면서 비교하지?라고 생각하였다.

- 직접 그려보고 이해해야겠당ㅠ

- 조건이 꽤 많은 것 같아서 하나라도 빠지지 않게 미리 작성해두고 진행해야 할 것 같다.

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

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

 

[백준 17136] 색종이 붙이기(Java)

 

자바(백준) 17136 색종이 붙이기