백준 BOJ 1780번

---

접근 방법

 

이 문제는 분할정복으로 풀면 된다. 분할정복은 따로 설명할 필요도 없이 쉬운 개념인데, 복잡한 큰 문제를 해결할 수 있는 단순한 부분 문제로 나누어 처리한 후 다시 합쳐서 해결하는 방법이다.

출처 : 나무위키 분할 정복 알고리즘

 

문제로 돌아와서, 해결 과정은 아래와 같다.

1. 종이가 모두 동일한 숫자인지 검사한다.
2. 아니라면 9개의 영역으로 나눈다.
3. 각 영역별로 1, 2번을 반복한다.

출처 :  https://st-lab.tistory.com/235

---

코드

import java.util.*;

public class Main {
   public static int[][] paper;
   public static int A = 0; // -1
   public static int B = 0; // 0
   public static int C = 0; // 1
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int N = in.nextInt();
      paper = new int[N][N];

      for(int i = 0; i < N; i++){
         for(int j = 0; j < N; j++){
            paper[i][j] = in.nextInt();
         }
      }
      Cut(0, 0, N);

      System.out.println(A);
      System.out.println(B);
      System.out.println(C);
   }
   public static void Cut(int row, int col, int size){
      if(check(row, col, size)){
         if(paper[row][col] == -1) 
            A++;
         else if(paper[row][col] == 0)
            B++;
         else 
            C++;
         return;
      }
      int next = size / 3;

      Cut(row, col, next);								    
		Cut(row, col + next, next);
		Cut(row, col + 2 * next, next);
		Cut(row + next, col, next);	
		Cut(row + next, col + next, next);		
		Cut(row + next, col + 2 * next, next);		
		Cut(row + 2 * next, col, next);			
		Cut(row + 2 * next, col + next, next);		
		Cut(row + 2 * next, col + 2 * next, next);
   }
   
   // 같은 숫자인지 체크하는 메소드
   public static boolean check(int row, int col, int size) {
      int num = paper[row][col];

      for(int i = row; i < row + size; i++){
         for(int j = col; j < col + size; j++){
            if(num != paper[i][j]) return false;
         }
      }
      return true;
   }
}