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

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

2630번: 색종이 만들기

---

 

해석 및 팁

 

---

 

이 문제는 분할정복을 사용하는 문제입니다. 색상이 모두 같은 경우가 아니라면 4개로 쪼개서 다시 색상을 확인합니다. 4개로 쪼개는 것은 재귀함수를 활용하면 되고 색상이 모두 같은 경우만 색상을 확인하여 카운트해 주면 됩니다.

https://namu.wiki/w/분할%20정복%20알고리즘

분할 정복 알고리즘 - 나무위키

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {

  static int col;
  static int n;
  static int w;
  static int b;
  static int[][] arr;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();
    
    n = sc.nextInt();
    arr = new int[n][n];

    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) arr[i][j] = sc.nextInt();
    }

    div(0, 0, n);

    sb.append(w+"\n"+b);
    
    System.out.println(sb);
  }

  public static void div(int x, int y, int r) {
    for(int i = x; i < x + r; i++) {
      for(int j = y; j < y + r; j++) {
        col = arr[x][y];
        if(col != arr[i][j]) {
          div(x, y, r / 2);
          div(x + r / 2, y , r / 2);
          div(x, y + r / 2 , r / 2);
          div(x + r / 2, y + r / 2 , r / 2);
          return;
        }
      }
    }
    
    if(col == 0) w++;
    else b++;
  }
}