Baekjoon | Q.2630 - 색종이 만들기

2630번: 색종이 만들기

 재귀 호출을 이용한 분할 정복 알고리즘을 구현하는 문제이다. 

import java.util.Scanner;

class Main {
  static int N;
  static int[][] paper;
  static int blue = 0;
  static int white = 0;

  public static void main(String[] args) {
    // 입력
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    paper = new int[N][N];

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

    sc.close();

    solution(0, 0, N);
    
    System.out.println(white);
    System.out.println(blue);
  }

  static boolean partition(int x, int y, int l) {
    boolean isSame = true;

    for (int i = x; i < x + l; i++) {
      for (int j = y; j < y + l; j++) {
        if(paper[i][j] != paper[x][y]) {
          isSame = false;
          break;
        }
      }
    }

    if(isSame) {
      if(paper[x][y] == 1) blue ++;
      else white ++;
    }

    return isSame;
  }

  static void solution(int x, int y, int l) {
    boolean isSame = partition(x, y, l);
    if(!isSame) { // 색종이가 같은 색상이 아닌경우
      solution(x, y, l/2);  // 4등분
      solution(x+l/2, y, l/2);
      solution(x, y+l/2, l/2);
      solution(x+l/2, y+l/2, l/2);
    }
  }
}

 나눠진 색종이가 같은 색상인지 확인하는 함수 partition()과 partition 실행 결과 색종이가 같은 색상이 아닌 경우에는 solution() 함수를 재귀호출 하는 방식으로 풀어주었다.