백준 : 17136

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

17136번: 색종이 붙이기

생각해보기

처음 단순 완전탐색을 생각햇을때 실수햇던점은 처음 1이 나온시점에서 DFS가 실패하면 그다음 칸으로가서 DFS를 실행한다. 이럴 경우 1이라는 숫자를 처리하지않고 DFS를 가는것은 명백한 시간오버를 야기할수 있었다.

 

두번째로는 처음 그칸을 기준으로 오른쪽 밑으로 색종이를 채울때 가장 큰것을 채우는것이 제일 효율적인 방법인가?

이문제는 아래의 case를 생각해보자.

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

 

처음에 5를 놔두면 이맵은 더이상 채울수 없게된다. 따라서 5~1까지 모든사이즐 각 좌표에대해서 검증을 해야한다.

또한 DFS(y,x)로 접근하기보단 seq 를 만들어 y x로 바꾸는 것이 이전에 검사했던 곳을 반복하지 않는다.

 

또한 이문제에 특정조건은 처음에 1이 나와서 DFS를 수행햇을때 재귀를 거쳐 다시 원래지점으로 돌아온 직후

그 다음 칸으로 진행하면 안된다. 왜냐면 이전칸의 1을 지우지 못한채 다음 칸으로 가는것은 죽은 가지를 가는 것과 같다.

package com.ssafy.Backjoon;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B17136 {
    static int N = 10;
    static int Map[][] = new int[N][N];
    static int minValue;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        // 입력 끝
        int cnt_one = 0;
 
        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());
                // 1이 남은 숫자
                if (Map[i][j] == 1)
                    cnt_one++;
            }
        }
 
        int[] colpaper = { 0, 5, 5, 5, 5, 5 };
        minValue = Integer.MAX_VALUE;
 
        DFS(0, 0, cnt_one, Map, colpaper);
 
        if (minValue == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(minValue);
        }
 
    }
 
    public static void DFS(int seq, int cnt, int cnt_one, int[][] map, int[] colpaper) {
 
        if (minValue <= cnt)
            return;
 
        if (cnt_one == 0) {
            minValue = Math.min(minValue, cnt);
            return;
        }
 
        int[][] copyMap = new int[N][N];
        
        boolean isbreak = false;
        
        for (int s = seq; s < N * N; s++) {
            int i = s / N;
            int j = s % N;
            if (map[i][j] == 0 || map[i][j] == 2)
                continue;
 
            for (int size = 5; size >= 1; size--) {
                if (colpaper[size] == 0)
                    continue;
 
                if (isPosible(i, j, size, map)) {
                    // copyMap 만들어서 다음 dfs
                    for (int yy = 0; yy < N; yy++) {
                        System.arraycopy(map[yy], 0, copyMap[yy], 0, map[yy].length);
                    }
 
                    // copyMap에 2로 마킹하기
                    for (int yy = i; yy < i + size; yy++) {
                        for (int xx = j; xx < j + size; xx++) {
                            copyMap[yy][xx] = 2;
                        }
                    }
                    isbreak =true;
                    colpaper[size]--;
                    DFS(s, cnt + 1, cnt_one - size * size, copyMap, colpaper);
                    colpaper[size]++;
 
                }
 
            }
            if(isbreak) return;
 
        }
 
    }
 
    public static boolean isPosible(int y, int x, int size, int[][] map) {
 
        if (y + size > N || x + size > N)
            return false;
 
        for (int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                if (map[i][j] != 1)
                    return false;
            }
        }
 
        return true;
    }
}