자바(백준) 17136 색종이 붙이기

오답 노트 & 새로 알게 된 점

 

처음 풀이

빨간색 1을 만날 때 모든 방향을 다 조사해야하나 라는 생각이 들었다.

하지만 1이 있는 곳 모두 완탐을 하게 되면 오른쪽 아래(초록색) 부분만 하면 된다는 생각을 했다.

 

완전 탐색을 하는데 처음엔 bfs를 사용하여 구현해보려했다.

하지만 색종이를 붙였다 떼었다 하는 과정이 필요할 것 같아서 백트래킹까지 생각했다.

 

A배열을 건들지 않으면서 백트래킹을 진행했다.

checkPaper메서드에서는 범위를 넘지 않고, A배열의 값은 1이면서 visit하지 않은 곳이 존재하면 색종이를 붙일 수 없다 판단했다.

 

하지만 시작점을 넣고 그 다음점을 어떻게 찾을지 계속 고민했다.

왜냐하면 위에서 완전 탐색을 할 것이기 때문에, (1,1)에서 dfs를 시작하고 나서

그 다음엔 처음부터 visit하지 않은 곳에서 다시 dfs를 시작해야했다.

 

이 방법을 통하여 해결하려 했으나 구현에서 막혀 해답을 보았다.

 

풀이

처음 풀이와 다른 점이 있다면 A배열을 건들고 다음 좌표는 dfs를 통하면서 하나씩 늘려준다.

 

전체적인 틀을 보면 (0,0) 부터 시작하여 y를 1씩 늘려주면서,

y 가 index 밖으로 나갈 경우 x를 1 증가시키고, y는 0부터 즉, 다음 행부터 시작한다.

 

dfs 종료 조건문을 보면 x >= 9 && y > 9 가 있다.

이 부분은 마지막 탐색이 x = 9, y = 10 까지 가기 때문이다.

x >= 9 && y >= 9를 하게 되면 마지막 (9,9)에 1이 있을 수 있어 오류를 범하게 된다.

 

addPaper 메서드가 신선했다.

state 파라미터를 사용하여 A배열을 바꾸는 것이다.

visit를 이용하여 문제를 해결하려 했을 때, 

아니 이걸 다 visit = true로 하고 또 다시 visit = false로 하나? 이런 생각이 들었다..

그런데 그렇게 하는 것이 놀라웠고, 앞으로 이게 되나라고 하기보다는 먼저 해보고 깨달아보자.

 

---

코드

package BackTracking;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ17136 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int A[][] = new int[10][10];
    static int paper[] = {0, 5, 5, 5, 5, 5};
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        dfs(0, 0, 0);
 
        if(ans == Integer.MAX_VALUE) ans = -1;
 
        System.out.println(ans);
    }
 
    static void dfs(int x, int y, int cnt) {
        if(x >= 9 && y > 9){
            ans = Math.min(ans, cnt);
            return;
        }
 
        if(cnt >= ans) return;
 
        if(y > 9){
            dfs(x + 1, 0, cnt);
            return;
        }
 
        if(A[x][y] == 1){
            for (int i = 5; i >= 1; i--) {
                if (paper[i] > 0 && checkPaper(x, y, i)) {
                    paper[i]--;
                    addPaper(x, y, i, 0);
                    dfs(x, y + 1, cnt + 1);
                    paper[i]++;
                    addPaper(x, y, i, 1);
                }
            }
        }
        else{
            dfs(x, y + 1, cnt);
        }
    }
 
    private static void addPaper(int x, int y, int size, int state) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                A[i][j] = state;
            }
        }
    }
 
    private static boolean checkPaper(int x, int y, int size) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if(!isRangeTrue(i,j) || A[i][j] == 0) return false;
            }
        }
        return true;
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < 10 && y >= 0 && y < 10;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                A[i][j] = atoi(st.nextToken());
            }
        }
    }
}
 

 

---

Reference

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