백준 : 분할정복

백준 : 색종이 만들기(2630) with 자바

유민기 2023. 9. 12. 00:53

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

 

2630번: 색종이 만들기

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

www.acmicpc.net

NxN 색종이를 입력받은 후 정사각형이 될 때까지 나눈다. 그리고 최종적으로 나누어진 하얀색, 파란색 색종이의 개수를 출력하면 되는 문제이다.

입출력을 살펴보자.

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

 

1. 8x8배열을 입력

2. 1번 나눈다. 이때 4 사분면에는 정사각형이 완성되었으므로 나머지 1, 2, 3사분면만 나눈다.

3. 1, 2, 4 사분면은 2번 나누었을 때 정사각형이 완성되었으므로 3사분면만 분할 해준다.

4. 최종적으로 white, blue의 색종이의 개수를 새어보면 각각 9, 7임을 확인할 수 있다.

바로 코드를 구현해보자.

import java.util.Scanner;

public class 색종이만들기 {
       public static int[][] map;
       public static int white;
       public static int blue;
       public static void main(String[] args){
             Scanner sc = new Scanner(System.in);
             int N = sc.nextInt();
             map = new int[N][N];
             for(int i=0; i < N; i++){
                  for(int j=0; j < N; j++){
                       map[i][j] = sc.nextInt();
                  }
             }
            partition(0, 0, N);
            System.out.println(white);
            System.out.println(blue);
      }
      public static void partition(int row, int col, int size){
             if(colorCheck(row, col, size)){
                if(map[row][col] == 0){
                   white++;
                }
                else{
                       blue++;
                }
                return;
            }
            int newSize = size / 2;
            partition(row, col, newSize);
            partition(row, col + newSize, newSize);
            partition(row + newSize, col, newSize);
            partition(row + newSize, col + newSize, newSize);
 
     }
     public static boolean colorCheck(int row, int col, int size){
          int color = map[row][col];
          for(int i = row; i < row + size; i++){
               for(int j = col; j< col + size; j++){
                    if(map[i][j] != color){
                       return false;
                    }
               }
          }
          return true;
     }
}

전역변수 white, blue 색종이의 색을 나타내는 변수와 숫자의 배열을 입력받을 map[][]을 생성해준다.

Scanner를 생성해주고 배열의 크기 N을 입력받는다.

map 배열에 [N][N]으로 저장하여 크기를 지정한 뒤 반복문을 돌려서 map[i][j]입력받은 배열을 읽어들인다.

partition함수를 호출하여 계산을 처리한뒤 white, blue 각각의 개수를 출력할 것이다.

 

분할 계산을 할 partition함수이다.

row, col, size 각각 행, 열, 크기를 의미한다.

현재 영역이 하얀색이라면 white++를 해주고

현재 영역이 파란색이라면 blue++를 해준다.

 

현재 영역을 1,2,3,4 사분면으로 나누어서 분할을 한뒤 재귀를 통해 계산을 해줄 것이다.

newSize 변수를 선언하고 size/2라고 정의해준다.

2사분면 = partition(row, col, newSize)

1사분면 = partition(row, col + newSize, newSize)

3사분면 = partition(row + newSize, col, newSize)

4사분면 = partition(row + newSize, col + newSize, newSize)
위와같이 4분면을 계산한다.

마지막으로 색종이의 색깔을 확인하기위한 함수이다. boolean을 사용하여 false, true를 사용하여 색종이의 check여부를 확인하려 한다.

partition과 마찬가지로 row, col, size를 선언한다.

현재 영역의 색이 무엇인지를 color에 저장한다.

반복문을 사용하여 행과 열에 현재색깔과 다른색이 있는지 검사를 해준다.

만약 다른색이 하나라도 있다면 false를 반환해준다.

모두 같은 색일 경우 반복문을 빠져나와 true를 반환해준다.

저작자표시 (새창열림)