Baekjoon[17136] - 색종이붙이기

링크

17136번: 색종이 붙이기

문제설명

• 완전탐색

문제풀이

• 완전탐색 + {1~5}색종이 붙이고 말고 DFS
• 백트래킹 - 시간관리

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static int Ans=Integer.MAX_VALUE;
    public static int Temp=0;
    public static int[][] map = new int[10][10];
    public static int[][] n_map = new int[10][10];
    public static int[] cnt = {0,5,5,5,5,5};

    public static boolean is_end() {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if(n_map[i][j]==1)return false;
            }
        }

        return true;
    }

    public static boolean coverable(int[]rc ,int range) {

        for (int i = 0; i < range; i++) {
            for (int j = 0; j < range; j++) {
//                경계 안이고
                if(rc[0]+i >=0 && rc[0]+i <10 && rc[1]+j>=0 && rc[1]+j<10) {
                    if(n_map[rc[0]+i][rc[1]+j]==0)return false;
                }
//                경계 밖으로 넘어가면
                else {
                    return false;
                }
            }
        }

        return true;
    }

    public static void cover(int[]rc, int range) {

        for (int i = 0; i < range; i++) {
            for (int j = 0; j < range; j++) {
                n_map[rc[0]+i][rc[1]+j]=0;
            }
        }
    }

    public static void recover(int[]rc, int range) {
        for (int i = 0; i < range; i++) {
            for (int j = 0; j < range; j++) {
                n_map[rc[0]+i][rc[1]+j] = map[rc[0]+i][rc[1]+j];
            }
        }
    }

    public static void Search(int[] rc) {
//        맵 끝까지 다 탐색했을 때,
        if(is_end()) {
            Ans = Math.min(Ans, Temp);
            return;
        }

//        열 끝까지 갔으면 행 한칸 밑으로 감
        if(rc[1]==10) {
            rc[1]=0;
            rc[0]++;
        }

//        덮어야 하는 칸이면
        if(n_map[rc[0]][rc[1]]==1) {
//          12345순서보다 54321이 최소해를 더빨리 찾음
            for (int i = 5; i >= 1; i--) {
//                백트래킹
                if(Temp>=Ans)return;
//                색종이가 여유있고, 덮을 수 있을 경우
                if(cnt[i]>0 && coverable(rc, i)) {
//                    cnt && 색종이덮기 && 색종이 갯수 소모
                    Temp++;
                    cnt[i]--;
                    cover(rc,i);
                    Search(new int[] {rc[0],rc[1]+1});
//                    원상복구
                    recover(rc, i);
                    cnt[i]++;
                    Temp--;
                }
            }
        }
        else {
            Search(new int[] {rc[0],rc[1]+1});
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        //System.setIn(new FileInputStream("res/baekjoon/17136.txt"));
        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());
                n_map[i][j] = map[i][j];
            }
        }

        Search(new int[] {0,0});

//        답 없는 경우
        if(Ans==Integer.MAX_VALUE)Ans=-1;
        System.out.println(Ans);
//        초기화
        Ans=0;
    }
}

아쉬운점

• 맵 덮어씌우고 하는거 i,j index 더해주는거 안함. map[r+i][c+j]
• coverable의 경우 경계밖으로 튀어나갈 수 있음, 경계검사 해야함.
• -1 나오는 경우 생각안했음
• 시간 애매하게 딱맞게 통과함... 근데 시간 줄여도 채점시간은 똑같았음
  • 그리디 자체는 못써도 탐색에서 그리디는 쓸 수 있을 것.
  • 1,2,3,4,5 순서대로 붙이는거보다
  • 5,4,3,2,1 순서대로 붙이는게 작은 답이 나올 확률이 높음->시간 줄일수 있음.

탐색 선택 순서에 따른 시간차이

잘한점

• 그리디 안씀
  • 6x6
    • 5x5 먼저 붙이면 손해임
    • 3x3 4개가이득
• DFS 구성함
• 백트래킹함 (Temp>Ans)return;
• {1~5} 선택하는 기준정하고, 복구하는거 다 함