[문제풀이] B1780 종이의 개수

종이의 개수

---

  🪅. 재귀를 이용해서 분할할 수 있는가 => 파라미터로 '시작좌표', 'size' 필요

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

  public class B1780_종이의개수 {
      static int N;
      static int[][] arr2d;
      static int cntM1;
      static int cnt0;
      static int cnt1;

      public static boolean checkValid(int x, int y, int size) {
          int std = arr2d[x][y];
          for(int i = x; i < x + size; i++) {
              for(int j = y; j < y + size; j++) {
                  if(std != arr2d[i][j]) return false;
              }
          }
          return true;
      }
      public static void partition(int x, int y, int size) {
          if(checkValid(x, y, size)) {
              switch(arr2d[x][y]) {
              case -1:
                  cntM1++;
                  break;
              case 0:
                  cnt0++;
                  break;
              case 1:
                  cnt1++;
                  break;    
              }

              return;
          }

          int splitedSize = size / 3;
          partition(x, y, splitedSize);
          partition(x, y + splitedSize, splitedSize);
          partition(x, y + (2*splitedSize), splitedSize);

          partition(x + splitedSize, y, splitedSize);
          partition(x + splitedSize, y + splitedSize, splitedSize);
          partition(x + splitedSize, y + (2*splitedSize), splitedSize);

          partition(x + (2*splitedSize), y, splitedSize);
          partition(x + (2*splitedSize), y + splitedSize, splitedSize);
          partition(x + (2*splitedSize), y + (2*splitedSize), splitedSize);
      }
      public static void init() throws NumberFormatException, IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          N = Integer.parseInt(br.readLine());
          arr2d = new int[N][N];
          StringTokenizer token;
          for(int i = 0; i < N; i++) {
              token = new StringTokenizer(br.readLine(), " ");
              for(int j = 0; j < N; j++) {
                  arr2d[i][j] = Integer.parseInt(token.nextToken());
              }
          }
      }
      public static void main(String[] args) throws NumberFormatException, IOException {
          init();
          partition(0, 0, N);
          System.out.println(cntM1);
          System.out.println(cnt0);
          System.out.println(cnt1);
      }
  }

💡. 문제 접근 과정
: partition(분할) 하는 과정에서 재귀를 이용해야겠다는 생각을 했다.
문제에서 종이를 같은 크기의 종이 9개로 자르라고 했으니까, 시작좌표와 size를 파라미터로 넘겨,
한 재귀마다 파라미터가 다른 9개의 재귀(?)를 만들어 문제를 해결했다.
재귀의 종료조건은 모든 재귀가, 파라미터로 넘겨진 범위의 원소가 1개가 되었을 때 무조건 checkValid를 통과하게 된다.
(물론, 그 이전에 종료조건을 만족해서 재귀가 끝날 수 있다.)
그래서 조건을 만족해서 종료되는 경우 이외의 종료조건을 두지 않았다.