[백준 17136] - 색종이 붙이기(JAVA)[골드2]

문제

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

17136번: 색종이 붙이기

문제 풀이

모든 좌표에 대해서 종이를 계속 바꿔가면서 붙이고, 최소한의 종이 개수를 구하면 될 것이라고 판단했다.

 

이유는

1. 배열의 크기가 그렇게 크지 않다.
   1. 10*10이므로 n^2이더라도 넉넉하다고 생각했다.
2. 종이의 종류가 많지 않다.
   1. 즉 하나의 좌표에서 종이의 종류대로 붙여가면서 확인을 하더라도 크게 시간이 오래 걸리지 않을 것 같았다.

따라서 나는 종이가 들어갈 수 있는 좌표에 대해서 모든 종이의 경우의 수를 붙여가면서 확인을 했다.

 

보통 이런 방법을 백트래킹이라고 하는데 간단하게 설명하면

선택지를 통해서 탐색을 하고, 탐색을 마치면 다른 선택지로 탐색을 시작하고, 모든 선택지를 탐색한다.

 

우리 문제를 예로 들면,

5 x 5 종이를 붙이고, 끝까지 탐색을 하고, 탐색을 마친 뒤 4 x 4 , 3 x 3.... 이렇게 모든 경우의 수를 탐색하는 것이다.

이런 방법은 n이 그렇게 크지 않았기에 가능한 방법이다.

 

어떻게 보면 DFS랑 동일하게 보일 수도 있고, 실제로 흐름은 동일하다.

하지만 백트래킹은 불필요한 탐색을 하지 않는다는 것이 차이이다.

 

우리는 최소한의 종이의 개수를 구하고 있는데, 탐색을 하는 과정에서 이미 붙인 종이의 개수가

구한 최솟값보다 크거나 같을 경우 굳이 탐색을 할 필요가 있을까?

 

이런 것을 백트래킹에서 Promising(유망성 검사)이라고 하는데 해당 내용까진 자세히 알 필요는 없지만,

간단하게는 탐색할 필요가 없을 경우 탐색을 중지한다고 이해하면 편할 것이다.

만약 백트래킹에 대해서 보충설명이 필요하다면 아래 글을 참고하도록..ㅎ

https://jja2han.tistory.com/30

[C++]-백트래킹(Backtracking)이란? + n-Queens문제

 

코드 흐름에 대해서 간단한게 설명하자면

1. 종이를 붙일 수 있는 구역을 ArrayList에 저장
2. count가 answer보다 크거나 같다면 탐색을 중지함. (유망성 검사)
3. DFS의 depth를 통해서 해당 좌표를 검사함.
4. 방문처리가 된 좌표라면 DFS(depth+1,count)를 호출해서 다음 단계를 진행
5. 종이의 사이즈 별로 해당 좌표에 붙일 수 있는지 없는지 검사함.
   • 종이가 없거나, 해당 좌표에 종이를 붙일 수 없다면 무시함.
6. 종이를 붙일 수 있다면 종이의 개수를 감소시키고, 방문처리
7. DFS(depth+1, count+1) 호출
8. 재귀를 탈출했다면 종이의 개수를 복원시키고, 6번에서 방문처리했던 좌표들을 다시 초기화.
9. [2,3,4,5,6,7,8]을 반복하다가 depth가 끝까지 간 경우 결과값을 업데이트하고 다시 [2,3,4,5,6,7,8]을 진행

해당 풀이는 코드를 보기보단, 근거를 가지고 풀이방법을 도출한 과정을 보는 것이 더 도움이 될 것 같다.

풀이에 자세한 설명은 코드의 주석을 통해서 참고하면 좋을 것 같다.

전체 코드

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static boolean[][] graph = new boolean[10][10];
    static ArrayList<Point> candidate = new ArrayList<>();
    static ArrayList<Paper> paper;
    static int limit;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        DFS(0, 0);
        if (answer == Integer.MAX_VALUE) {
            System.out.print(-1);
        } else {
            System.out.print(answer);
        }
    }

    public static void input() throws IOException {
        int num;
        for (int i = 0; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                num = Integer.parseInt(st.nextToken());
                if (num == 0) {
                    graph[i][j] = false;
                } else {
                    graph[i][j] = true;
                    candidate.add(new Point(i, j));
                }
            }
        }
        paper = new ArrayList<Paper>();
        for (int i = 1; i <= 5; i++) {
            paper.add(new Paper(i));
        }
        limit = candidate.size();
    }

    public static void DFS(int depth, int count) {
        if (depth == limit) { //끝까지 왔을때
            answer = Math.min(answer, count);
            return;
        }
        Point now = candidate.get(depth);
        if (answer <= count) { //최소개수보다 많을 경우 더이상 탐색하지 않아도 됨.
            return;
        }
        if (!graph[now.x][now.y]) { //이미 채워져있다면
            DFS(depth + 1, count);
        } else {
            for (int i = 4; i >= 0; i--) {
                if (paper.get(i).amount == 0 || !resemblePaper(paper.get(i).size, now.x, now.y)) { //종이가 없을 때,해당 좌표에 종이를 끼워넣을 수 없을 때
                    continue;
                }
                paper.get(i).amount--; //종이 사용하기 ,
                fillPaper(paper.get(i).size, now.x, now.y); //종이 넣었다고 표시
                DFS(depth + 1, count + 1); // 깊이 증가, 종이 갯수 추가
                paper.get(i).amount++; //종이 채우기.
                fillPaper(paper.get(i).size, now.x, now.y); // 종이 넣은거 표시 취소
            }
        }
    }

    public static boolean resemblePaper(int size, int row, int col) { //주어진 범위 내에 종이를 넣지 못하는지 파악.
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (i >= 10 || j >= 10 || !graph[i][j])
                    return false;
            }
        }
        return true;
    }

    public static void fillPaper(int size, int row, int col) {
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                graph[i][j] = !graph[i][j];
            }
        }
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Paper {
        int size;
        int amount = 5;

        public Paper(int size) {
            this.size = size;
        }
    }
}