[SWEA] 17136번 : 색종이 붙이기

진짜 참 어렵다....

왜 이걸 푼다고 하필 오늘...

결국 답을 봤고,,,이해하고 나서 내 코드로 바꿔보려고 했는데 실-패 ㅠㅠ

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

 

결국 풀이를 생각해내지 못해서, 아래 블로그를 참고했다!!

https://steady-coding.tistory.com/43

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

 

 

 

이건 어떻게 풀었냐?!

x, y를 하나씩 증가 시키면서 p 배열에 사용할 수 있는 종이 개수를 담아둔다.

첫번째. 붙일 수 있는지 체크하고

두번째. 붙이는 게 가능하다면 붙이면 된다.

만약에 붙일 수 없으면 그냥 함수를 나와버린다.

여기서 dfs 를 돌려서 끝점에 도달하면 그때 최소값을 구하고, 

static void solve(int x, int y, int depth) {
        // 겹쳐도 안 된다.
        // 0 이 적힌 칸에는 색종이 없어야 한다.

        // 맨 끝점
        if(x>=9 && y>9) {
            ans = Math.min(ans, depth);
            return;
        }

        // 가지 치기
        // 최소 구해야 함
        // 근데 ans 가 depth 보다 커지면 탐색 X
        if(ans<=depth) return;

        // 아래 줄로 이동
        if(y>9) {
            solve(x+1, 0, depth);
            return;
        }

        if(map[x][y]==1) {
            for(int i=5;i>=1;i--) {
                // 1. check (붙일 수 있는지)
                if(p[i]>0 && check(x, y, i)) {
                    // 2. attach (가능 하면 붙여)
                    attach(x, y, i, 0); // 색종이 붙이고
                    p[i]--;
                    solve(x, y+1, depth+1);
                    attach(x, y, i, 1); // 다시 떼
                    p[i]++;
                }
            }
        }
        else {
            // 오른쪽 으로 이동
            solve(x, y+1, depth);
        }

    }

 

현재 좌표를 기준으로 범위 체크와 1인지 아닌지를 확인해준다. 이때 size에 맞게 1이 다 있으면 색종이를 붙일 수 있으니까 true를 리턴한다.

// 1. check
    static boolean check(int x, int y, int s) {
        for(int i=x;i<x+s;i++) {
            for(int j=y;j<y+s;j++) {
                // 범위를 벗어 나면
                if(i<0 || i>=10 || j<0 || j>=10) return false;
                // 범위에 있어도 1이 아니면
                if(map[i][j]!=1) return false;
            }
        }
        return true;
    }

 

그리고 범위 체크를 위에서 했으면 그냥 붙여주기만 하면 된다. 

// 2. attach
    static void attach(int x, int y, int s, int val) {
        for(int i=x;i<x+s;i++) {
            for(int j=y;j<y+s;j++) {
                map[i][j] = val;
            }
        }
    }

[전체코드]

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

class Main {

//    static int n;
    static int map[][], ans;
    static int p[] = {0, 5, 5, 5, 5, 5};

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

//        int T = Integer.parseInt(br.readLine());

//        for(int tc=1;tc<=T;tc++) {

            map = new int[10][10];
            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());
                }
            }

            // 1
            // 2 * 2 = 4
            // 3 * 3 = 9
            // 4 * 4 = 16
            // 5 * 5 = 25
            ans = Integer.MAX_VALUE;
            solve(0, 0, 0);
            System.out.println(ans==Integer.MAX_VALUE ? -1 : ans);

            br.close();
//        }

    }

    static void solve(int x, int y, int depth) {
        // 겹쳐도 안 된다.
        // 0 이 적힌 칸에는 색종이 없어야 한다.

        // 맨 끝점
        if(x>=9 && y>9) {
            ans = Math.min(ans, depth);
            return;
        }

        // 가지 치기
        // 최소 구해야 함
        // 근데 ans 가 depth 보다 커지면 탐색 X
        if(ans<=depth) return;

        // 아래 줄로 이동
        if(y>9) {
            solve(x+1, 0, depth);
            return;
        }

        if(map[x][y]==1) {
            for(int i=5;i>=1;i--) {
                // 1. check (붙일 수 있는지)
                if(p[i]>0 && check(x, y, i)) {
                    // 2. attach (가능 하면 붙여)
                    attach(x, y, i, 0); // 색종이 붙이고
                    p[i]--;
                    solve(x, y+1, depth+1);
                    attach(x, y, i, 1); // 다시 떼
                    p[i]++;
                }
            }
        }
        else {
            // 오른쪽 으로 이동
            solve(x, y+1, depth);
        }

    }

    // 1. check
    static boolean check(int x, int y, int s) {
        for(int i=x;i<x+s;i++) {
            for(int j=y;j<y+s;j++) {
                // 범위를 벗어 나면
                if(i<0 || i>=10 || j<0 || j>=10) return false;
                // 범위에 있어도 1이 아니면
                if(map[i][j]!=1) return false;
            }
        }
        return true;
    }

    // 2. attach
    static void attach(int x, int y, int s, int val) {
        for(int i=x;i<x+s;i++) {
            for(int j=y;j<y+s;j++) {
                map[i][j] = val;
            }
        }
    }

}

 

이건 내가 바꿔보려고 시도한 코드...굳이 y를 증가시키는걸 재귀로 돌렸어야하나? 싶어서

for문으로 했는데 이러면 return 되면서 백트래킹에 문제가 생긴다...쩝...

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

class Main {

    //    static int n;
    static int map[][], ans;
    static boolean flag=true;
    static int p[] = {0, 5, 5, 5, 5, 5};

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

//        int T = Integer.parseInt(br.readLine());

//        for(int tc=1;tc<=T;tc++) {

        map = new int[10][10];
        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());
            }
        }

        // 1
        // 2 * 2 = 4
        // 3 * 3 = 9
        // 4 * 4 = 16
        // 5 * 5 = 25
        ans = Integer.MAX_VALUE;
        solve(0, 0,0);
        System.out.println(ans==Integer.MAX_VALUE ? -1 : ans);

        br.close();
//        }

    }

    static void solve(int x, int y, int depth) {
        if(ans<=depth) return;

        if(x>9) {
            ans = Math.min(ans, depth);
            flag = false;
            return;
        }

        for(int j=y;j<10;j++) {
            if(map[x][j]==1) {
                for (int i = 5; i >= 1; i--) {
                    if (p[i] > 0 && check(x, j, i)) {
                        attach(x, j, i, 0);
                        p[i]--;
                        solve(x, j+1, depth + 1);
                        p[i]++;
                        attach(x, j, i, 1);
                    }
                }
            }
        }

        if(flag) solve(x+1, 0, depth);

    }

    static boolean check(int x, int y, int val) {
        for(int i=x;i<x+val;i++) {
            for(int j=y;j<y+val;j++) {
                // 범위 벗어남
                if(i<0 || i>=10 || j<0 || j>=10) return false;
                // 1이 아니면
                if(map[i][j]!=1) return false;
            }
        }
        return true;
    }

    static void attach(int x, int y, int s, int val) {
        for(int i=x;i<x+s;i++) {
            for(int j=y;j<y+s;j++) {
                map[i][j]=val;
            }
        }
    }

}