[JAVA] 백준 색종이 만들기

import java.util.Scanner;

public class Main {
    static int blue = 0, white = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[][] list = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                list[i][j] = sc.nextInt();
            }
        }
        sc.close();

        // 분할 정복 시작
        countPapers(list, 0, 0, N);

        System.out.println(white);
        System.out.println(blue);
    }

    static void countPapers(int[][] list, int x, int y, int size) {
        if (checkPaper(list, x, y, size)) {
            if (list[x][y] == 1) {
                blue++;
            } else {
                white++;
            }
            return;
        }

        int newSize = size / 2;
        countPapers(list, x, y, newSize);                   // 좌상단
        countPapers(list, x, y + newSize, newSize);         // 우상단
        countPapers(list, x + newSize, y, newSize);         // 좌하단
        countPapers(list, x + newSize, y + newSize, newSize); // 우하단
    }

    static boolean checkPaper(int[][] list, int x, int y, int size) {
        int color = list[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (list[i][j] != color) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

풀이

1. 좌우상하 모서리로 구역을 큰부분부터 나눠서 계산한다. 8*8, 4*4, 2*2, 1*1 이런식으로 진행된다.

2. 그 구역을 확인했을 때 완료된다면 해당 구역은 더 이상 검사하지않는다.

 

느낀점

코딩테스트 문제중에 이런문제들이 되게 많았던 것 같은데 실제 코딩테스트에서는 본적이 없던것같다. 근데 풀이를 이해해놓으면 좋은 것 같다. 재귀적사고와 구역을 분할하는 능력이 도움될 것 같다.

 

 

 

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