[BOJ] 색종이 붙이기(JAVA)

[17136] 색종이 붙이기

www.acmicpc.net/problem/17136

 

Solution

• 색종이를 붙일 수 있는 칸에(findDot()) 대해서 1~5 사이즈의 색종이를 붙이고(isValid() & drawing()) 지워가며(removing()) count가 가장 작은 값을 answer에 저장했다.
• 처음에 접근했던 방식은 map[i][j] 값이 1인 dot들을 List에 넣고, 순서대로 뽑아서 색종이를 붙이는 식으로 구현했는데 이 경우에는 위 6, 7번 예제의 답이 제대로 나오지 않아서 findDot()으로 칸을 찾도록 만들었다.

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int answer;
    static int[][] map;
    static int[] paper = {0, 5, 5, 5, 5, 5};
 
    static class Dot {
        private int x;
        private int y;
 
        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[10][10];
        int count = 0;
        StringTokenizer st;
        for (int i = 0; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                map[i][j] = stoi(st.nextToken());
                if (map[i][j] == 1) {
                    map[i][j] = -1;
                    count++;
                }
            }
        }
 
        answer = Integer.MAX_VALUE;
        if (count > 0) {
            dfs(0);
            answer = (answer == Integer.MAX_VALUE) ? -1 : answer;
        } else {
            answer = 0;
        }
 
        System.out.println(answer);
    }
 
    private static void dfs(int count) {
        Dot dot = findDot();
 
        if (dot.x == -1 && dot.y == -1) {
            answer = Math.min(answer, count);
            return;
        }
 
        int x = dot.x;
        int y = dot.y;
 
        for (int i = 1; i <= 5; i++) {
            if (paper[i] == 0) continue;
            if (isValid(x, y, i)) {
                drawing(x, y, i);
                paper[i]--;
                dfs(count + 1);
                paper[i]++;
                removing(x, y, i);
            } else {
                return;
            }
        }
    }
 
    private static Dot findDot() {
        Dot dot = new Dot(-1, -1);
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map.length; j++) {
                if (map[i][j] == -1) {
                    dot.x = i;
                    dot.y = j;
                    return dot;
                }
            }
        }
        return dot;
    }
 
    private static void removing(int x, int y, int size) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                map[i][j] = -1;
            }
        }
    }
 
    private static void drawing(int x, int y, int size) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                map[i][j] = size;
            }
        }
    }
 
    private static boolean isValid(int x, int y, int size) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (i < 0 || j < 0 || i >= 10 || j >= 10 || map[i][j] != -1) {
                    return false;
                }
            }
        }
        return true;
    }
 
    private static int stoi(String s) {
        return Integer.parseInt(s);
    }
 
}