[백준 1992번 Java] 쿼드트리

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

1992번: 쿼드트리

---

        if(check(n, x, y)){
            System.out.printf("%d, %d, %d 압축 가능 : ", n, x, y);
            result += map[x][y];
            System.out.println(map[x][y]);
        }

 

반례를 확인했는데 에러가 뜸

https://www.acmicpc.net/board/view/115294

[반례]
40000111100001111
정답 : ((0011)(0011)(0011)(0011))

 

    public static boolean check(int n, int x, int y){
        int f = map[y][x];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(map[y+i][x+j] != f) {
                    return false;
                }
            }
        }
        return true;
    }

 

반례도 다 해봣는데..

잘 출력되는데..

틀렸대

왜지?

 

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class bj_1992 {
    static int[][] map;
    static String result = "";
    public static void dfs(int n, int x, int y){
        //호출된 크기의 block 압축이 될 수 있다면
        if(check(n, x, y)){
//            System.out.printf("%d, %d, %d 압축 가능 : ", n, x, y);
            result += map[y][x];
            return;
//            System.out.println(map[y][x]);
        }

        //압축이 될 수 없다면
        //
        else {
//            System.out.printf("%d, %d, %d 압축 불가능 : ", n, x, y);
            result += '(';
//            System.out.println("(");
            dfs(n/2, x,  y);
            dfs(n/2, x +n/2,  y);
            dfs(n/2, x,  y +n/2);
            dfs(n/2, x+n/2,  y+n/2);

            result += ')';
//            System.out.println(")");
        }
    }

    public static boolean check(int size, int x, int y) {
        int value = map[x][y];

        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                if(value != map[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        map = new int[n][n];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = s.charAt(j) - 48;
            }
        }

        dfs(n, 0, 0);
        System.out.println(result);
    }
}

 

https://st-lab.tistory.com/230