[백준 2630] 색종이 만들기 (Java)

이 문제는 직전에 풀었던 종이의 개수와 비슷한 문제이다.

모두 같은 색인지 확인한 뒤, 같다면 해당 색깔의 종이 갯수를 1 증가시키고, 그렇지 않다면 4분할하여 같은 과정을 반복해나가면된다.

따라서, 백준 1780번(종이의 개수)와 굉장히 유사하다는 것을 알 수 있다.

여기서, 모두 같은 색인지 확인하는 동작과 4분할하는 동작을 구분하여 구현하면 문제가 쉽게 풀린다.

이를 코드로 옮기면 다음과 같다.

import java.util.*;

public class Main {
  private static final Scanner input = new Scanner(System.in);
  private static int n;
  private static int[][] board;
  private static int blue;
  private static int white;

  public static void main(String[] args) {
    n = input.nextInt();
    board = new int[n][n];
    for (int i = 0; i < board.length; i++) {
      for (int j = 0; j < board[i].length; j++) {
        board[i][j] = input.nextInt();
      }
    }

    solve(0, 0, n);

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

  public static void solve(int r, int c, int size) {
    if (check(r, c, size)) {
      if (board[r][c] == 1) blue++;
      else white++;
      return;
    }

    int nSize = size / 2;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        solve(r + i * nSize, c + j * nSize, nSize);
      }
    }
  }

  public static boolean check(int r, int c, int size) {
    for (int i = r; i < r + size; i++) {
      for (int j = c; j < c + size; j++) {
        if (board[r][c] != board[i][j]) return false;
      }
    }
    return true;
  }
}