백준 1780 종이의 개수 Java 풀이

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 이 있는데, 하나의 숫자로만 이루어진 정사가형의 개수를 세어서 -1, 0, 1 순서로 출력하라

 

출처 : https://www.acmicpc.net/problem/1780

접근

이전에 풀었던 백준 2630 색종이 만들기의 조금 다른 버전의 문제이다.

기본적으로 동일한데 종이를 4등분이 아닌 9등분을 한다는 사실과 -1, 0, 1 순서로 출력한다는 사실이 다르다.

따라서 백준 2630 색종이 만들기 문제를 조금더 확장성 있게 바꿔서 풀면 된다.

 

역시 시간 복잡도는 O(N^2) 이다.

풀이

public class Main {
    private static int[][] BOARD;
    private static final int NEXT_SQUARE_COUNT = 9;
    private static final Map<Integer, Integer> COUNT = new TreeMap<>(){{
        put(-1, 0);
        put(0, 0);
        put(1, 0);
    }};

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

        // 입력 초기화
        int N = Integer.parseInt(br.readLine());
        BOARD = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                BOARD[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 분할,정복
        divideAndCount(0, 0, N, NEXT_SQUARE_COUNT);

        // 출력

        COUNT.forEach((key, count) -> System.out.println(count));
    }

    private static void divideAndCount(int x, int y, int size, int divide) {
        if (isOneColor(x, y, size)) {
            COUNT.put(BOARD[x][y], COUNT.getOrDefault(BOARD[x][y], 0) + 1);
            return;
        }

        int sqrtDivide = (int) Math.sqrt(divide); // 가로/세로로 나누는 개수
        int newSize = size / sqrtDivide;          // 각 분할 영역의 크기

        // sqrtDivide 만큼 행과 열을 분할하여 재귀 호출
        for (int i = 0; i < sqrtDivide; i++) {
            for (int j = 0; j < sqrtDivide; j++) {
                divideAndCount(x + i * newSize, y + j * newSize, newSize, divide);
            }
        }
    }

    /**
     *
     * @param x BOARD 탐색 시작 행 INDEX
     * @param y BOARD 탐색 시작 열 INDEX
     * @param size i+size, j+size 까지 탐색
     * @return {true: 모두 같은 색상만 있음 ,false: 서로 다른 색상이 있음}
     */
    private static boolean isOneColor(int x, int y, int size) {
        int color = BOARD[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (color != BOARD[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}